reactos/boot/environ/lib/misc/util.c

   1 /*
   2  * COPYRIGHT:       See COPYING.ARM in the top level directory
   3  * PROJECT:         ReactOS UEFI Boot Library
   4  * FILE:            boot/environ/lib/misc/util.c
   5  * PURPOSE:         Boot Library Utility Functions
   6  * PROGRAMMER:      Alex Ionescu (alex.ionescu@reactos.org)
   7  */
   8
   9 /* INCLUDES ******************************************************************/
  10
  11 #include "bl.h"
  12
  13 /* DATA VARIABLES ************************************************************/
  14
  15 PVOID UtlRsdt;
  16 PVOID UtlXsdt;
  17
  18 PVOID UtlMcContext;
  19 PVOID UtlMcDisplayMessageRoutine;
  20 PVOID UtlMcUpdateMessageRoutine;
  21
  22 PVOID UtlProgressRoutine;
  23 PVOID UtlProgressContext;
  24 PVOID UtlProgressInfoRoutine;
  25 ULONG UtlProgressGranularity;
  26 ULONG UtlCurrentPercentComplete;
  27 ULONG UtlNextUpdatePercentage;
  28 BOOLEAN UtlProgressNeedsInfoUpdate;
  29 PVOID UtlProgressInfo;
  30
  31 /* FUNCTIONS *****************************************************************/
  32
  33 VOID
  34 BlUtlUpdateProgress (
  35     _In_ ULONG Percentage,
  36     _Out_opt_ PBOOLEAN Completed
  37     )
  38 {
  39     if (UtlProgressRoutine)
  40     {
  41         EfiPrintf(L"Unimplemented\r\n");
  42     }
  43     else if (*Completed)
  44     {
  45         *Completed = TRUE;
  46     }
  47 }
  48
  49 NTSTATUS
  50 BlUtlInitialize (
  51     VOID
  52     )
  53 {
  54     UtlRsdt = 0;
  55     UtlXsdt = 0;
  56
  57     UtlMcContext = 0;
  58     UtlMcDisplayMessageRoutine = 0;
  59     UtlMcUpdateMessageRoutine = 0;
  60
  61     UtlProgressRoutine = 0;
  62     UtlProgressContext = 0;
  63     UtlProgressInfoRoutine = 0;
  64     UtlProgressGranularity = 0;
  65     UtlCurrentPercentComplete = 0;
  66     UtlNextUpdatePercentage = 0;
  67     UtlProgressNeedsInfoUpdate = 0;
  68     UtlProgressInfo = 0;
  69
  70     return STATUS_SUCCESS;
  71 }
  72
  73 PVOID
  74 BlTblFindEntry (
  75     _In_ PVOID *Table,
  76     _In_ ULONG Count,
  77     _Out_ PULONG EntryIndex,
  78     _In_ PBL_TBL_LOOKUP_ROUTINE Callback,
  79     _In_ PVOID Argument1,
  80     _In_ PVOID Argument2,
  81     _In_ PVOID Argument3,
  82     _In_ PVOID Argument4
  83     )
  84 {
  85     PVOID Entry = NULL;
  86     ULONG Index;
  87     BOOLEAN Result;
  88
  89     /* Check for invalid parameters */
  90     if (!(Table) || !(EntryIndex))
  91     {
  92         return Entry;
  93     }
  94
  95     /* Loop each entry in the table */
  96     for (Index = 0; Index < Count;  Index++)
  97     {
  98         /* Check if this entry is filled out */
  99         if (Table[Index])
 100         {
 101             /* Call the comparison function */
 102             Result = Callback(Table[Index],
 103                               Argument1,
 104                               Argument2,
 105                               Argument3,
 106                               Argument4);
 107             if (Result)
 108             {
 109                 /* Entry fouund return it */
 110                 *EntryIndex = Index;
 111                 Entry = Table[Index];
 112                 break;
 113             }
 114         }
 115     }
 116
 117     /* Return the entry that was (or wasn't) found */
 118     return Entry;
 119 }
 120
 121 NTSTATUS
 122 BlTblSetEntry (
 123     _Inout_ PVOID** Table,
 124     _Inout_ PULONG Count,
 125     _In_ PVOID Entry,
 126     _Out_ PULONG EntryIndex,
 127     _In_ PBL_TBL_SET_ROUTINE Callback
 128     )
 129 {
 130     ULONG NewCount;
 131     NTSTATUS Status = STATUS_SUCCESS;
 132     ULONG Index = 0;
 133     PVOID* NewTable;
 134
 135     /* Make sure all the parameters were specified */
 136     if (!(Table) || !(*Table) || !(Count) || !(Callback))
 137     {
 138         return STATUS_INVALID_PARAMETER;
 139     }
 140
 141     /* Read the current table */
 142     NewTable = *Table;
 143     NewCount = *Count;
 144
 145     /* Iterate over it */
 146     while (Index < NewCount)
 147     {
 148         /* Look for a free index */
 149         if (!NewTable[Index])
 150         {
 151             goto SetIndex;
 152         }
 153
 154         /* No free index yet, keep going */
 155         ++Index;
 156     }
 157
 158     /* No free index was found, try to purge some entries */
 159     Index = 0;
 160     while (Index < NewCount)
 161     {
 162         /* Call each purge callback, trying to make space */
 163         Status = Callback(NewTable[Index]);
 164         if (NT_SUCCESS(Status))
 165         {
 166             /* We should have this slot available now */
 167             goto SetIndex;
 168         }
 169
 170         /* Keep trying to purge more */
 171         ++Index;
 172     }
 173
 174     /* Double the table */
 175     NewTable = BlMmAllocateHeap(2 * sizeof(PVOID) * NewCount);
 176     if (!NewTable)
 177     {
 178         return STATUS_NO_MEMORY;
 179     }
 180
 181     /* Clear the new table, and copy the old entries */
 182     RtlZeroMemory(&NewTable[NewCount], sizeof(PVOID) * NewCount);
 183     RtlCopyMemory(NewTable, *Table, sizeof(PVOID) * NewCount);
 184
 185     /* Free the old table */
 186     BlMmFreeHeap(*Table);
 187
 188     /* Return the new table and count */
 189     *Count = 2 * NewCount;
 190     *Table = NewTable;
 191
 192 SetIndex:
 193     /* Set the index and return */
 194     NewTable[Index] = Entry;
 195     *EntryIndex = Index;
 196     return Status;
 197 }
 198
 199 NTSTATUS
 200 BlTblMap (
 201     _In_ PVOID *Table,
 202     _In_ ULONG Count,
 203     _In_ PBL_TBL_MAP_ROUTINE MapCallback
 204     )
 205 {
 206     NTSTATUS Status, LocalStatus;
 207     PVOID Entry;
 208     ULONG Index;
 209
 210     /* Bail out if there's no table */
 211     if (!Table)
 212     {
 213         return STATUS_INVALID_PARAMETER;
 214     }
 215
 216     /* Assume success and loop each index */
 217     Status = STATUS_SUCCESS;
 218     for (Index = 0; Index < Count; Index++)
 219     {
 220         /* See if an entry exists at this index */
 221         Entry = Table[Index];
 222         if (Entry)
 223         {
 224             /* Call the map routine for this entry */
 225             LocalStatus = MapCallback(Entry, Index);
 226             if (!NT_SUCCESS(LocalStatus))
 227             {
 228                 /* Propagate failure only */
 229                 Status = LocalStatus;
 230             }
 231         }
 232     }
 233
 234     /* Return status to caller */
 235     return Status;
 236 }
 237
 238 ULONG HtTableSize;
 239 PBL_HASH_TABLE* HtTableArray;
 240 ULONG HtTableEntries;
 241
 242 ULONG
 243 DefaultHashFunction (
 244     _In_ PBL_HASH_ENTRY Entry,
 245     _In_ ULONG TableSize
 246     )
 247 {
 248     PUCHAR Value;
 249     ULONG KeyHash, i;
 250
 251     /* Check if the value is a pointer, or embedded inline */
 252     Value = (Entry->Flags & BL_HT_VALUE_IS_INLINE) ? Entry->Value : (PUCHAR)&Entry->Value;
 253
 254     /* Iterate over each byte, and sum it */
 255     for (i = 0, KeyHash = 0; i < Entry->Size; i++)
 256     {
 257         KeyHash += Value[i++];
 258     }
 259
 260     /* Modulo the number of buckets */
 261     return KeyHash % TableSize;
 262 }
 263
 264 BOOLEAN
 265 HtpCompareKeys (
 266     _In_ PBL_HASH_ENTRY Entry1,
 267     _In_ PBL_HASH_ENTRY Entry2
 268     )
 269 {
 270     ULONG Flags;
 271     BOOLEAN ValueMatch;
 272
 273     /* Check if the flags or sizes are not matching */
 274     Flags = Entry1->Flags;
 275     if ((Entry1->Size != Entry2->Size) || (Flags != Entry2->Flags))
 276     {
 277         ValueMatch = FALSE;
 278     }
 279     else if (Flags & BL_HT_VALUE_IS_INLINE)
 280     {
 281         /* Check if this is an in-line value, compare it */
 282         ValueMatch = Entry1->Value == Entry2->Value;
 283     }
 284     else
 285     {
 286         /* This is a pointer value, compare it */
 287         ValueMatch = (RtlCompareMemory(Entry1->Value, Entry2->Value, Entry1->Size) ==
 288                       Entry1->Size);
 289     }
 290
 291     /* Return if it matched */
 292     return ValueMatch;
 293 }
 294
 295 NTSTATUS
 296 TblDoNotPurgeEntry (
 297     _In_ PVOID Entry
 298     )
 299 {
 300     /* Never purge this entry */
 301     return STATUS_UNSUCCESSFUL;
 302 }
 303
 304 NTSTATUS
 305 BlHtCreate (
 306     _In_ ULONG Size,
 307     _In_ PBL_HASH_TABLE_HASH_FUNCTION HashFunction,
 308     _In_ PBL_HASH_TABLE_COMPARE_FUNCTION CompareFunction,
 309     _Out_ PULONG Id
 310     )
 311 {
 312     NTSTATUS Status;
 313     PBL_HASH_TABLE HashTable;
 314     ULONG i;
 315
 316     /* Assume failure */
 317     HashTable = NULL;
 318
 319     /* Can't create a table with no ID */
 320     if (!Id)
 321     {
 322         return STATUS_INVALID_PARAMETER;
 323     }
 324
 325     /* Check if we don't already have a hash table table */
 326     if (!HtTableSize)
 327     {
 328         /* Allocate it and zero it out */
 329         HtTableSize = 4;
 330         HtTableArray = BlMmAllocateHeap(HtTableSize * sizeof(PVOID));
 331         if (!HtTableArray)
 332         {
 333             Status = STATUS_NO_MEMORY;
 334             goto Quickie;
 335         }
 336         RtlZeroMemory(HtTableArray, HtTableSize * sizeof(PVOID));
 337         HtTableEntries = 0;
 338     }
 339
 340     /* Allocate the hash table */
 341     HashTable = BlMmAllocateHeap(sizeof(*HashTable));
 342     if (!HashTable)
 343     {
 344         Status = STATUS_NO_MEMORY;
 345         goto Quickie;
 346     }
 347
 348     /* Fill it out */
 349     HashTable->HashFunction = HashFunction ? HashFunction : DefaultHashFunction;
 350     HashTable->CompareFunction = CompareFunction ? CompareFunction : HtpCompareKeys;
 351     HashTable->Size = Size ? Size : 13;
 352
 353     /* Allocate the hash links, one for each bucket */
 354     HashTable->HashLinks = BlMmAllocateHeap(sizeof(LIST_ENTRY) * HashTable->Size);
 355     if (!HashTable->HashLinks)
 356     {
 357         Status = STATUS_NO_MEMORY;
 358         goto Quickie;
 359     }
 360
 361     /* Initialize the hash links */
 362     for (i = 0; i < HashTable->Size; i++)
 363     {
 364         InitializeListHead(&HashTable->HashLinks[i]);
 365     }
 366
 367     /* Save us in the table of hash tables */
 368     Status = BlTblSetEntry((PVOID**)&HtTableArray,
 369                            &Size,
 370                            HashTable,
 371                            Id,
 372                            TblDoNotPurgeEntry);
 373     if (NT_SUCCESS(Status))
 374     {
 375         /* One more -- we're done */
 376         ++HtTableEntries;
 377         return Status;
 378     }
 379
 380 Quickie:
 381     /* Check if we just allocated the table array now */
 382     if (!(HtTableEntries) && (HtTableArray))
 383     {
 384         /* Free it */
 385         BlMmFreeHeap(HtTableArray);
 386         HtTableArray = NULL;
 387         HtTableSize = 0;
 388     }
 389
 390     /* Check if we allocated a hash table*/
 391     if (HashTable)
 392     {
 393         /* With links? */
 394         if (HashTable->HashLinks)
 395         {
 396             /* Free them */
 397             BlMmFreeHeap(HashTable->HashLinks);
 398         }
 399
 400         /* Free the table*/
 401         BlMmFreeHeap(HashTable);
 402     }
 403
 404     /* We're done */
 405     return Status;
 406 }
 407
 408 NTSTATUS
 409 BlHtLookup (
 410     _In_ ULONG TableId,
 411     _In_ PBL_HASH_ENTRY Entry,
 412     _Out_opt_ PBL_HASH_VALUE *Value
 413     )
 414 {
 415     PBL_HASH_TABLE HashTable;
 416     ULONG HashValue;
 417     NTSTATUS Status;
 418     PLIST_ENTRY HashLinkHead, HashLink;
 419     PBL_HASH_NODE HashNode;
 420
 421     /* Check if the table ID is invalid, or we have no entry, or it's malformed */
 422     if ((HtTableSize <= TableId) ||
 423         !(Entry) ||
 424         ((Entry->Flags & BL_HT_VALUE_IS_INLINE) && (Entry->Size != sizeof(ULONG))))
 425     {
 426         /* Fail */
 427         Status = STATUS_INVALID_PARAMETER;
 428     }
 429     else
 430     {
 431         /* Otherwise, get the hash table for this index */
 432         HashTable = HtTableArray[TableId];
 433
 434         /* Get the hash bucket */
 435         HashValue = HashTable->HashFunction(Entry, HashTable->Size);
 436
 437         /* Start iterating each entry in the bucket, assuming failure */
 438         Status = STATUS_NOT_FOUND;
 439         HashLinkHead = &HashTable->HashLinks[HashValue];
 440         HashLink = HashLinkHead->Flink;
 441         while (HashLink != HashLinkHead)
 442         {
 443             /* Get a node in this bucket, and compare the value */
 444             HashNode = CONTAINING_RECORD(HashLink, BL_HASH_NODE, ListEntry);
 445             if (HashTable->CompareFunction(&HashNode->Entry, Entry))
 446             {
 447                 /* Does the caller want the value? */
 448                 if (Value)
 449                 {
 450                     /* Return it */
 451                     *Value = &HashNode->Value;
 452                 }
 453
 454                 /* Return success and stop scanning */
 455                 Status = STATUS_SUCCESS;
 456                 break;
 457             }
 458
 459             /* Try the next node */
 460             HashLink = HashLink->Flink;
 461         }
 462     }
 463
 464     /* Return back to the caller */
 465     return Status;
 466 }
 467
 468 NTSTATUS
 469 BlHtStore (
 470     _In_ ULONG TableId,
 471     _In_ PBL_HASH_ENTRY Entry,
 472     _In_ PVOID Data,
 473     _In_ ULONG DataSize
 474     )
 475 {
 476     PBL_HASH_NODE HashNode;
 477     NTSTATUS Status;
 478     PLIST_ENTRY HashLinkHead;
 479     PBL_HASH_TABLE HashTable;
 480
 481     /* Check for invalid tablle ID, missing arguments, or malformed entry */
 482     if ((HtTableSize <= TableId) ||
 483         !(Entry) ||
 484         !(Data) ||
 485         !(Entry->Size) ||
 486         !(Entry->Value) ||
 487         !(DataSize) ||
 488         ((Entry->Flags & BL_HT_VALUE_IS_INLINE) && (Entry->Size != sizeof(ULONG))))
 489     {
 490         /* Fail the call */
 491         Status = STATUS_INVALID_PARAMETER;
 492         goto Quickie;
 493     }
 494
 495     /* Get the hash table for this ID */
 496     HashTable = HtTableArray[TableId];
 497
 498     /* Allocate a hash node */
 499     HashNode = BlMmAllocateHeap(sizeof(*HashNode));
 500     if (!HashNode)
 501     {
 502         Status = STATUS_NO_MEMORY;
 503         goto Quickie;
 504     }
 505
 506     /* Capture all the data*/
 507     HashNode->Entry.Size = Entry->Size;
 508     HashNode->Entry.Flags = Entry->Flags;
 509     HashNode->Entry.Value = Entry->Value;
 510     HashNode->Value.DataSize = DataSize;
 511     HashNode->Value.Data = Data;
 512
 513     /* Insert it into the bucket list and return success */
 514     HashLinkHead = &HashTable->HashLinks[HashTable->HashFunction(Entry, HashTable->Size)];
 515     InsertTailList(HashLinkHead, &HashNode->ListEntry);
 516     Status = STATUS_SUCCESS;
 517
 518 Quickie:
 519     return Status;
 520 }
 521