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

Я згадував, шо працюю зараз над імплементацією 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 у нас уже під логаритмом. Погодьтесь, різниця є.
Отже підсумовуючи. Структура БД вибрана з огляду на семантику сервісів, які в свою чергу вибрані такими, творцями специфікації з огляду на зручність їхнього використання в клієнтах. БД організована як таблиця гендлів, яка є фрагментований (можливо) динамічний масив. Кожен гендл має таблицю протоколів, які на ньому інстальовані - це нефрагментований масив. І кожен протокол має таблицю агентів, які його споживають на цьому гендлі - ця таблиця теж нефрагментована. Дефрагментація досягається переміщенням крайнього елементу на видаленні як згадано вище. Фрагментованість таблиці гендлів іде як ціна від прискорення через використання адреси структури гендла як його значення, для його ідентифікації. Але фрагментованість очікується низька. До того ж система всеодно має можливість дефраґментувати таблицю на вставленнях.
Нарешті, для прискорення пошукових сервісів, які мають як ключ пошуку протокол, вводиться допоміжна структура - словник протоколів в системі, імплементований як двійкове червоно-чорне дерево пошуку, з високими показниками ефективности пошуку.
Пізніше я додам іллюстрацію, а в наступній статті, проаналізую функції додавання/видалення на описаних структурах, які відбуваються на сервісах інсталяції/деінсталяції гендлів/протоколів/агентів.
Така ось крива й коса ілюстрація бази даних гендлів. може колись я навчусь краще робити ілюстрації, а покишо ось: