Завантажувальні сервіси - Сервіси обслуговування протоколів

В попередьному дописі було зроблено огляд БД гендлів і описано пошукові сервіси, які працюють на цій БД. Тепер опишемо сервіси, які вставляють і видаляють елементи.
Коротко нагадаємо структуру БД. Вона складається з таблиць і дерева.

• Таблиця (структур) гендлів, одна на всю систему, вона може бути фраґментована і дефраґментація може лише відбуватися на вставленні нових елементів. В разі переповнення можливе лише пряме розширення. В разі неуспіху його - крах системи.
• Таблиця (структур) протоколів. По одній на кожен валідний гендл. Містить масив протоколів, інстальованих на цьому гендлі. Ця таблиця нефраґментована - завсіди на видаленні протокола з гендла, крайній елемент таблиці переноситься в новоутворену від видалення дірку, і масив завсіди лишається суцільним. Може бути розширена прямо, або через перевиділення нового більшого буферу і копіювання старої таблиці туди.
• Таблиця агентів. По одній на кожен протокол (в масиві протоколів на гендлі). Так само - нефраґментована таблиця, розширювана прямо і через копіювання в крайньому разі.
• Дерево протоколів. Одне на всю систему. Червоно-чорне двійкове дерево пошуку. Грає роль словника - містить усі унікальні протоколи, які були інстальовані на систему під час однієї сесії. Це публічна інофрмація за протокол, глобальна для всієї системи - словник. Приватна - це масиви протоколів на гендлах. Ми не видаляємо вузол взагалі, він може бути інстальований знову, і це добра оптимізація. До того ж, нам не треба робити видалення на червоно-чорних деревах, а це дуже марудна справа.
• Масив вказівників на структури гендлів (з таблиці гендлів). По одному на кожен вузол словника протоколів. Нефраґментована, розширювна прямо і через копіювання таблиця.

Ці два останні елементи - словник з дерева і масиви вказівників на гендл на вузлах дерева - дуже важлива частина БД покликана пришвидшувати пошукові сервіси, які шукають через протокол. Ще одна оптимізація - це відсутність видалення на вузлах цього словника. Якшо протокол видаляється з системи загалом, ми, замість робити страшну процедуру видалення на червоно-чорному дереві, просто занулюємо довжину таблиці вказівників на вузлі, ми навіть не звільняємо сам масив вказівників. Якшо драйвер спробує інсталювати цей протокол знову, все шо нам треба зробити на вузлі, це інкрементувати згадану довжину, і додати в масив вказівник на гендл. А не вставляти вузол знову, який насправді забирає всього пару десятків байтів. Дуже добре. Усе дерево не забере багато навіть разом з масивами вказівників, але пршивдшення пошуку очевидне.
Отже, ми маємо гендли на кожному з яких є таблиця істальованих на нього протоколів, і маємо дерево протоколів, на кожному вузлі якого є таблиця вказівників на гендл, на яких цей протокол істальований. Ця надлишковість дуже пришвидшує пошук за протоколом і не дуже ускладнює сервіси видалення/вставлення.
Які вони? Специфікація встановлює такі:

• InstallProtocolInterface()
• ReinstallProtocolInterface()
• UninstallProtocolInterface()
• InstallMultipleProtocolInterfaces()
• UninstallMultipleProtocolInterfaces()

Такі сервіси як OpenProtocol(), OpenProtocolInformation(), CloseProtocol(), ConnectController(), DisconnectController() будуть розглянуті окремо там, де це показуватиме якісь їхні особливості, - з точки зору операцій на БД, вони мають аналогічні ефекти, шо й згадані, лише на своїх таблицях - таблицях агентів. Наприклад OpenProtocol() додає агента, якшо все йде успішно, до таблиці агентів на протоколі, інстальованому на гендлі. CloseProtocol() очевидно робить зворотню роботу. OpenProtocolInformation() читає таблицю агентів. З цим відстежуванням агентів в БД складність полягає не в тому як організована БД за шо ми зараз балакаємо, а з самою семантикою того відстежування - воно заслуговує окремого розгляду. Так як і синхронізація на БД в тому числі.
Функції, які інсталюють або деінсталюють протокольні інтерфейси як вони представлені на рівні специфікації - суть функції, які взагалі будують БД, бо по-перше їхня базова функціональність уже диктує це, а по-друге, специфікація покладає на них неявну роботу з видалення/вставлення всієї ієрархії, наприклад якшо функція InstallProtocolInterface() отримує як значення гендла NULL, то вона має створити гендл, а потім вже інсталювати туди протокол. Так само, - ці функції беруть на себе тягар з побудови імплементцінйо-специфічної структури БД.
Спочатку про словник. Було вже згадано, шо видалення на словнику немає, це насправді дуже вигідно для нашого випадку - фірмваря матиме пам'ять для цього, а от робити зайву роботу не буде. Тож уся складність сервісів видалення - це складність визначена не структурою БД, а семантикою прив'язування агентів до протоколів. Це буде висвітлено окремо.
Переповнення масивів.
Ми вибрали організацію, коли може бути переповнення масивів, і, в разі цього, їх треба розширяти. Це було вибране як кращий варіант, за списки масивів. Розширення робиться спочатку спробою справді розширити виділену ділянку за допомгою внутрішнього сервісу пам'яти, а якшо виділити таке розширення не вдасться, тоді робиться виділення більшого буферу і копіювання старого туди. Це очікується як рідкісна подія. Єдина структура, яка не зможе бути перекопійована - це таблиця гендлів - значення гендлів (як змінних) це адреси структур гендлів в таблиці, якшо ми перенесемо таблицю, зміняться адреси, але клієнти користуються старими гендлами і оповіщати усіх про такі зміни нереалістично. Тобто ми можемо лише спробувати розширити цю таблицю прямо. Внутрішня функція для цього - MiExtendPool(). А взагалі, краще вгадати з кількістю гендлів з самого початку. Це розплата за константний час пошуку гендла.
InstallProtocolInterface(). З усього вище сказаного, витікає, шо більшість роботи пов'язаної з побудовою і перебудовою БД, лягає на цю функцію. Вона інсталює протокол на гендл, якшо треба - створює гендл. А значить, вона має вміти:

• вставляти протокол в словник (операція на червоно-чорному дереві - не найлегша операція) - "глобальна" інсталяція протоколу,
• вставляти гендл в таблицю - створення гендла,
• виділяти таблицю протоколів для новоствореного гендла,
• вставляти протокол в таблицю протоколів на гендлі - власне інсталяція протокола,
• вставляти вказівник на гендл в масив вказівників на вузлі дерева;

 а також:

• розширювати прямо таблицю гендлів,
• розширювати прямо або копіюванням таблицю протоколів,
• розширювати прямо або копіюванням масив вказівників на гендл.

"Multiple" варіанти сервісів (останні два в списку), які обробляють багато протоколів одразу, всередині викликають "одиничні" функції. Вони введені для "зручности" написання драйверів. З точки зору обслуговування БД, вони мають ту саму семантику. Варто також зазначити, шо OpenProtocol() робить те саме на таблицях агентів - створює її, додає туди елементи, розширює її прямо або копіюванням.
UninstallProtocolInterface(). Сервіс видалення, був би дуже складний, з т.з. БД, якби ми мали потребу справді видаляти вузол з словника. Але оскільки ми здогадались, шо цього насправді не треба робити - складність відпадає. Так само нема складности з розширенням навпаки - ми просто не робимо звуження масиву - це просто не потрібно. А от шо потрібно - робити дефраґментацію на видаленні, для нефраґментованих таблиць (а це масиви протоколів, масиви агентів і масиви вказівників на гендли). На видаленні, функція переносить крайній елемент таблиці в новостворену дірку. Також ми налаштовуємо поля в відповідних структурах - зменшуємо лічильник кількости елементів підлеглої таблиці (він же - індекс на першу вільну комірку таблиці). Ця функція робить дефраґментацію на таблицях протоколів і таблицях вказівників на гендли, а CloseProtocol() робить це на таблицях агентів. Декрементація лічильника робиться цією функцією на вузлах словника і гендлах (кількість гендлів і протоколів відповідно). На протоколах декрементація (кількість агентів) робиться CloseProtocol(). Деінсталяція гендла - це позначення поля валідности відповідної структури в стан "невалідний". І ще одна заввага - оскільки протоколи з словника не видаляються, може виникнути питання про стан тих записів протоколи яких насправді ніде не інстальовані (адже протоколи завсіди мають бути інстальвонаі на якийсь гендл). І як такі записи в словнику узгоджуються з консистентністю БД. Відповідь проста - поле кількости гендлів на масиві вказівників на гендл для такого вузла дорівнює нулю. Це і є ознака неістальованости протокола. З т.з. системи він не присутній в системі, - ніде не інстальований, але з т.з. імплементації ми покращили - спростили двигун БД і пришвидчили вставлення - якшо хтось захоче таки інсталювати цей протокол знову - ми вже маємо запис в словнику, і вставляти знову вузол не треба.
ReinstallProtocolInterface() - просто міняє вказівник на інтерфейс на протоколі інстальованому на гендлі. Там це "просто" - дешо складніше, але знову не з т.з БД, а з т.з. синхронізації і звязків між агентами і протоколами. Так же само як сервіси на агентах мають набагато більше мороки з цими зв'язками. Власне саме вони й обслуговують усю кашу з прив'язуванням драйверів і відслідкованим, контрольованим деінсталюванням/реінсталюванням. За це наступного разу.
Шодо виділення пам'яти. На цьому етапі, ми виділяємо пам'ять для структур з системного пулу, використовуючи функцію AllocatePool(). Це стосується всіх структур, крім таблиці гендлів, яка покишо не має імплементованої точки створення - це верхня ініціалізація фірмварі, вона ще не написана. Але там ми або так само використовуватимемо сервіси пулу, або сервіс сторінкового виділення. Невидно поки ніякої потреби тут створювати якийсь спеціальний алокаційний велосипед. Також ми додали внутрішню, вже згадану, функцію MiExtendPool(). Її прототип такий:

EFI_STATUS MiExtendPool(
   IN PVOID pBuffer,
   IN UINTN UnitSize,
   IN OUT PUINTN pUnitCount
   );

Вона розширює виділений за допомогою AllocatePool() буфер, на (UnitSize * (*pUnitCount)) байтів, якшо може, або на N одиніць довжиною UnitSize байтів, де 0 <= N <= UnitCount. І пише виділену кількість одиниць назад в змінну (*pUnitCount). Це дуже вдалий вибір логіки аргументів, бо з ним ми уникаємо проблеми невирівняного виділення. Справді, специфікація вимагає виділення з пулу робити вирівняними на 8 байтів - логічно і розумно. Шоб не створювати проблем, ми й виділювані блоки робитимемо цілим множником 8-ми. От уявімо наша структура протоколу має 24 байти в довжину. Якби ми просили просто розширити на скількись 8-батних блоків, могло б вийти неціле число 24-байтних блоків, тобто - неціле число одиниць протоколів. Тоді на другому розширенні, ми могли б мати хибну нестачу місця. Справді, уявімо, шо на першому розширенні масиву протоколів, функція розширення вернула нам 32 байти розширення. Нам вистачить і одного блоку (24 байти) на раз. Ми ділячи виділене на довжину нашого блоку взнаємо кількість нових місць, а зайве місце не чіпаємо. Але якшо нам знадобиться ще й вдруге доточувати масив, ми наприклад можемо зіткнутись з таким сценарієм і проблемою. Шоразу протяжного місця все менше, його може й не бути, отже вдруге функція може вернути лише 16 байтів. Цього не досить, і ми підемо перевиділяти місце і копіювати - дорога операція. Але насправді, ми мали 12 зайвих байтів уже, плюс 16 додано ще, - цього вистачить на один елемент! Але ми цього не бачимо, бо наша структура не має поля для "зайвого місця" - це було б кривобоко ліпити його туди. Отже, рішення полягає в запитуванні розширювати масив на кількість в блоках. Це не порушує внутрішнього алокаційного закону виділяти все на вирівняних на 8 адресах і виділяти цілими до 8-ми штуками; і робить доточування вільним від тієї кострубатости. Як воно не порушує? Ну, ми маємо просити так, шоб принаймні (UnitSize * UnitCount) ділився націло на 8, а краще й UnitSize мати таким, якшо можливо - нам це і так треба, - шоб не мати внутрішніх проблем з вирівнюванням в структурах. На 32-х платформах, вказівник на гендл - а ми маємо таку таблицю, 4-байтний. Ми отримаємо шонайменше 2 місця замість 1-го з ненульових. От і все. Ми  просто не маємо просити дати один 4-байтний блок - функція верне неуспіх. Доточування робиться так:

Noh = gProtocolArrayLength;
Status = MiExtendPool(pHandle->pProtocolArray, sizeof(PROTOCOL), &Noh);

Ми пишемо в змінну бажану кількість одиниць, на яку б ми хотіли доточити наш масив, і викликаємо функцію, а вона вертає в разі успіху, в цю змінну, - кількість одиниць, яку вона справді виділила, і ця кількість буде від нуля до нашої запитаної кількости. Тож, у випадку з 32-бітними платформами, функція шонайменше верне 2 з ненульвоих варіантів, адже всеодно семантика виділення на пулі диктує 8-байтне вирівнювання, і, як наслідок, - мінімальний блок виділення 8 байтів. В разі неуспіху, функція не чіпатиме масив і залишить все як було.
Цей сервіс дасть нам ще один шанс уникнути копіювання. А у випадку з таблицею гендлів - це єдина надія.

Завантажувальні сервіси - Структура бази даних гендлів

Я згадував, шо працюю зараз над імплементацією UEFI  десь так зсередини, тобто я не став вчити спочатку глибочезний апаратний низ якоїсь платформи і, відповідно, - писати такий собі Start.asm (це теж буде, а якже, але пізніше); я сів вчити саму UEFI, читати її специфікацію, і по ходу діла, бачачи, шо тут можна шось писати, почав це робити. Спочатку думав робити це у вигляді C-побідного псевдокоду, але потім виявилось, шо в принципі нічого не заважає намагатися робити повну імплементацію окремих принаймні функцій. Отже, "ядро" UEFI організоване в сервіси - набір функцій, які обслуговують різну функціональність - API, тільки прив'язується клієнт до нього не через статичне чи динамічне лінкування, а через таблицю диспетчеризації, яку ядро надає кожному завантаженому клієнтові. Це драйвери, застосунки, завантажувачі ОС (теж застосунки). Сервіси суть розбиті на дві категорії - Boot Services, базові сервіси доступні в т.зв. "передзавантажувальному" середовищі (pre-boot environment), тобто власне - в час роботи самої UEFI, і Runtime Services - сервіси часу виконання - виконання ОС мається на увазі, тобто це служби, які ОС може в себе викликати, якшо хоче. Вони доступні і під час передзавантажувального періоду, і після перехоплення контролю ОС, і ОС має розуміти і поважати їхню наявність, шоб могти ними користуватися.
Я, читаючи специфікацію, і дійшовши до детального опису завантажувальних сервісів (ЗС), а це глава 6-та в специфікації, вирішив засісти за імплементацію сервісів обслуговування протоколів, СОП, (Protocol Handler Sevices). Всі ЗС діляться на підкатегорії:

• Event and Timer Services - сервіси подій і таймерів 
• Task Priority Level Services - сервіси синхронізації за рівнем пріоритету завдання
• Memory Services - сервіси пам'яти (інтерфейс аллокатора пам'яти) 
• Protocol Handler Services - сервіси  обслуговування протоколів
• Image Services - сервіси завантажувача образів
• Miscelaneous Services - різне, наприклад сервіс підрахунку Crc32

З евентами, синхронізацією і тим паче - керуванням пам'яттю все дуже не ясно покишо, тож я засів за СОП (сервіси обслуговування протоколів). От про структури даних, повязані з цими сервісами я сьогодні і розкажу. Як я їх вирішув побудувати.
Ці структури даних організовуються в базу даних гендлів (Handle Data Base). Відповідно існує структура, яка цю базу описує. Це такий собі корінь. Уся база організована з структур двох типів, один з яких, - розбивається на 2 підтипи. Отже які об'єкти складають наші дані в роботі з СОП? Це гендли й протоколи. А також - агенти, які є набором гендлів з атрибутами. Інші об'єкти, які можуть використовуватися, але суть з інших категорій, такі як події і таймери, будуть розглянуті в своїх темах, а те, шо стосується їхнього використання в обслуговуванні протоколів, буде додано пізніше, бо як я вже сказав - синхронізація ще не розроблена взагалі. Я не описуватиму, шо значить кожна сутність визначена в UEFI, це треба читати специфікацію, я ж намагаюсь розказувати за імплементацію. Отже гендл це обєкт, який асоціюється з пристроєм, з образом (драйвера, застосунку або самого UEFI), - це персоналізація базового структруного елементу фірмварі. Протокол - це набір з імени і структури, яка містить вказівники на функції і дані, які цей протокол імплементує. Ім'я робиться у вигляді GUID'а.
Цікавий момент з протоколами полягає в тому, шо ідентифікуються вони саме за іменем, а от інтерфейс може бути різним, або взагалі не бути. Протоколи інсталюються на гендл, і там вони існують. Є функції які можуть переінсталювати той самий протокол помінявши в ньому вказівник на інтерфейс, конткретно, - це сервіс ReinstallProtocolInterface(). З цього й видно - шо хоч і здається, шо конткретний протокол має бути прив'язаний до конктретного його наповнення (інтерфейсної структури, - функцій, які він надає), це не зовсім так, і в системі можуть існувати два (або більше) гендли, на яких інстальовано той самий протокол, але інтерфейсні вказівники - різні. Але, з іншого боку, для системи - це один і той самий протокол. Це видно з опису певних функцій СОП. Наприклад функція LocateHandle() або LocateHandleBuffer(), якшо тип пошуку задано ByProtoocol, має просто вернути масив усіх гендлів "на яких інстальовано цей протокол". А протокол задається лише GUID'ом.
Отже ми маємо гендли. Сам тип, визначений специфікацією, - EFI_HANDLE, визначений як VOID * не зобов'язаний бути вказівником на шось. Тобто його значення має "непрозору" (opaque) семантику. Якась прив'язка цього значення до внутрішньої імплементації, вирішується самою імплементацією. І я вирішив використовувати для значення гендла адресу на структуру, яка його представляє. Це дає велику оптимізацію. Бо пошук гендла стає константним по часу - незалежним від кількости гендлів в системі. Ми просто приводимо гендл до типу вказівника на структуру гендла, і якшо треба, читаємо поле валідности - це дає ґарантію, шо ми не поліземо писати в незрозуміло яку ділянку памяти, і далі вже працюємо з гендловою структурою. Не треба нічого шукати взагалі. З іншого боку, адреси - унікальні, тож якшо ми маємо два гендли з різним значенням, вони представляють два різні гендли. І навпаки - два гендли з одним і тим значенням - це той самий гендл. Це оптимальне рішення звичайно має свою ціну - а саме - ми маємо фраґментацію таблиці гендлів. Гендли організовані в таблицю. Це просто масив структур. Висока локальність, без надмірности зберігання вказівників (як в списках чи деревах).  Це перший підтип табличних структур нашої бази. І лише гендли так організовані. Ця таблиця може бути фрагментована, оскільки раз виділивши гендл десь в таблиці, ми не можемо пересовувати його деінде доки він валідний. Це таблиця з непересувними елементами. Дефраґментація відбувається тільки на додаванні - ми вставляємо новий гендл не в край, а спочатку дивимося чи є дірки, якшо є, вставляємо в першу від початку, і тільки якшо нема дірок, вставляємо в край.
Другий табличний тип - це нефраґментовані таблиці. Елементи в них можуть бути пересунуті на видаленні (дивись нижче), тим самим просто підтримуючи протяжність таблиці. В такі таблиці організовані протоколи інстальовані на гендл, і таблиці агентів, які споживають конкретний протокол на конкретному гендлі. Спочатку я думав мати там списки, двонаправлені, закільцьовані, але прийшов до висновку, шо краще динамічні масиви. Знову - масиви дають максимальну локальність і займають менше місця. Вони лінійні по пошуку. Але тут питання кількости. Треба розуміти - ми маємо таблицю гендлів, на кожному гендлі інстальовано протоколи, і кожен протокол має скількись агентів, які його споживають. Просто неймовірно, шоб оці дві останні таблиці були довгими. Важко сказати, нажаль, це не легко оцінити, але, з іншого боку, очевидно - це не може бути великим числом. Тобто питання кількох одиниць на таблицю. Уявляєте якою надмірністю тут було б використовувати дерева! І з огляду на масштабованість - так само неймовірно, шо з часом ця кількість збільшиться, просто по суті - тут не може бути великої кількости елементів. Ну і якшо вже буде - тоді переробимо на дерева.
Як робитиметься дефраґментація. На видаленні якогось елемента (аґента чи протокола), функція, поміщатиме на його місце крайній елемент в списку. Спочатку здавалось, шо дефраґментація буде складним завданням і дорогою операцією. Потім прийшла здогадка про оцю релокацію на видаленні. Таблиця увесь час протяжна. І це досягається за константний час. Ми маємо індекс на перше вільне місце в струткурі, яка має цей масив. Наприклад в гендлі, ми маємо поле NumberOfProtocolInterfaces - це і кількість протоколів інстальованих на цьому гендлі, й індекс першої вільної клітини в масиві. Завдяки цьому полю ми маємо доступ до останнього елемнта константно. І таким чином можемо робити константне переміщення для дефраґментації. Ясно, шо якшо елемент, який видаляється останній, переміщення немає. Нажаль з причин уже вказаних вище, ми не можемо так робити з таблицею гендлів. Але там ми маємо константний доступ, а тут лінійний. Просто лінійність тут не буде повільною - ми маємо невелику кількість елементів. Надто невелику, шоб будувати тут дерева.
І третій тип в нашій базі. Це допоміжна структура. Це словник протоколів в системі. Як вже було відзначено, семантика протоколів взагалі робить їх більше приватними для гендла, згадайте хоча б свободу реінсталювати на протоколі інтерфейсний вказівник, - це має приватний обшир для конкретного гендла. З іншого боку, ми маємо кілька сервісних функцій, сенс яких аж вимагає мати системний словник для протоклів - адже попри волю в виборі інтерфейсу, протокол для системи - це його GUID і всі протоколи інстальовані на різних гендлах з одиним і тим же GUID'ом є одним і тим же протоколом. Саме для оптимізації пошуку за протоколом, ми вводимо третю допоміжну структуру - словник протоколів. Такі функції як LocateHandle() і LocateHandleBuffer(), якшо параметр пошуку є ByProtocol, а також LocateProtocol(), вони мають ключем пошуку саме протокол (його GUID). Очевидно якшо ми шукатимемо через таблицю гендлів, а потім через масив протоколів в кожному гендлі, ми матимемо жахливу залежність O(N*m') - де
N - це кількість гендлів системі (в таблиці), m' - це середня кілкість протоколів в таблиці протоколів кожного гендла. Інші ж функції, а саме ProtocolsPerHandle() , або вищезгадані перші дві, якшо параметр пошуку - AllHandles, виграють сильно в своїх операціях від використання таблиці гендлів. Адже без пошуку вони вже мають гендл, а потім просто видають список протоколів інстальвоаних на гендл, або видають всі гендли в системі - це лінійна робота за будь якої структури організації. Саме набір семантики оцих сервісів і диктував вибір організації підлеглої бази даних. Варто коротко нагадати які саме пошукові сервіси задані UEFI:

• Група яка має ключем протокол
• Група яка має ключем гендл

 Перша група, це функції, які як пошуковий ключ отримують протокол і видають гендл(и), на якому (яких) цей протокол інстальований.
Це такі функції:

• LocateHandle() , LocateHandleBuffer() за пошукового параметра ByProtocol - видають всі гендли які мають цей протокол інстальований
  
• LocateProtocol() - видає перший гендл на якому цей протокол інстальований

Друга група, отримує гендл як ключ (або директиву обійти всі гендли):

• ProtocolsPerHandle() - видає всі протоколи інстальовані на гендлі
• LocateHandle(), LocateHandleBuffer() за пошукового параметру AllHandles - видають всі гендли в системі

Саме через наявність отієї першої групи, з'явилась ідея додати третю допоміжну структуру - словник протоколів. Я не знаю, яка кількість протоколів в системі буде, але очевидно - це більше, ніж число протоколів інстальоване на конкретному гендлі. І того було вирішено зробити цей словник у вигляді червоно-чорного двійкового дерева пошуку. Пошук логаритмічний, локальність не дуже, але це як завсіди - баланс. Червоно-чорні дерева з точки зору операцій пошуку, суть такі самі як звичайні двійкові дерева. Отже зараз, коли ми поки не чіпаємо інсталяцію/деінсталяцію, можемо лише сказати, - словник протоколів, введений для пришвидшення пошуку на сервісах, які беруть протокол як пошуковий ключ. Це перша група сервісів. Це дублювання не складає ніяких проблем для цих пошукових сервісів, вони ці структури не будують, а лише читають. Але й сервіси, які будують, про які я розкажу наступного разу, вони навряд зустрінуть тут велику складність маючи необхідність додатково в добре визначених місцях алгоритму обслуговувати ще й дерево на додачу до таблиць. А виграш очевидний. В нашому дереві, кожен вузол - це протокол, і він має масив гендлів (саме гендлів а не структур гендлів як в таблиці гендлів). Цей масив будується як нефраґментована таблиця. І вона так само очікується вельми коротка. Отже порівнюючи. Наші сервіси першої групи за відсутністю допоміжного дерева мали б час пошуку O(N * m'), а з деревом матимуть O(n' * logM), де як уже казано:
N - число гендлів в системі,
m' - середнє число протоколів на гендлі
n' - середнє число гендлів на протоколі
M - число протоколів в системі
Очевидно, очікується, шо n' - буде вельми малим, - це кількість гендлів, на яких цей протокол інстальований. Багато протоколів будуть інстальовані взагалі на одному гендлі; ну а M у нас уже під логаритмом. Погодьтесь, різниця є.
Отже підсумовуючи. Структура БД вибрана з огляду на семантику сервісів, які в свою чергу вибрані такими, творцями специфікації з огляду на зручність їхнього використання в клієнтах. БД організована як таблиця гендлів, яка є фрагментований (можливо) динамічний масив. Кожен гендл має таблицю протоколів, які на ньому інстальовані - це нефрагментований масив. І кожен протокол має таблицю агентів, які його споживають на цьому гендлі - ця таблиця теж нефрагментована. Дефрагментація досягається переміщенням крайнього елементу на видаленні як згадано вище. Фрагментованість таблиці гендлів іде як ціна від прискорення через використання адреси структури гендла як його значення, для його ідентифікації. Але фрагментованість очікується низька. До того ж система всеодно має можливість дефраґментувати таблицю на вставленнях.
Нарешті, для прискорення пошукових сервісів, які мають як ключ пошуку протокол, вводиться допоміжна структура - словник протоколів в системі, імплементований як двійкове червоно-чорне дерево пошуку, з високими показниками ефективности пошуку.
Пізніше я додам іллюстрацію, а в наступній статті, проаналізую функції додавання/видалення на описаних структурах, які відбуваються на сервісах інсталяції/деінсталяції гендлів/протоколів/агентів.
Така ось крива й коса ілюстрація бази даних гендлів. може колись я навчусь краще робити ілюстрації, а покишо ось: