오리너구리

5장에서 알아낸 Generic Table의 내부 데이터 구조체

struct NODE
{
    NODE          *ParentNode;
    NODE          *RightChild;
    NODE          *LeftChild;
    LIST_ENTRY    LLEntry;
    ULONG         Unknown;
}

struct TABLE
{
    NODE                     *TopNode;
    LIST_ENTRY               LLHead;
    LIST_ENTRY               *LastElementFound;
    ULONG                    LastElementIndex;
    ULONG                    NumberOfElements;
    TABLE_COMPARE_ELEMENTS   CompareElements;
    TABLE_ALLOCATE_ELEMENT   AllocateElement;
    TABLE_FREE_ELEMENT       FreeElement;
    ULONG                    unknown;
};

Generic Table 콜백 함수에 대한 프로토타입

typedef int (NTAPI*TABLE_COMPARE_ELEMENTS) (TABLE *pTable, PVOID pElement1, PVOID pElement2);

typedef NODE * (NTAPI * TABLE_ALLOCATE_ELEMENT) ( TABLE *pTable, ULONG TotalElementSize );

typedef void (NTAPI * TABLE_FREE_ELEMENT) ( TABLE *pTable, PVOID Element );

기본적인 Generic Table API의 프로토타입

void NTAPI RtlInitializeGenericTable(
    TABLE *pGenericTable,
    TABLE_COMPARE_ELEMENTS ComapreElements,
    TABLE_ALLOCATE_ELEMENT AllocateElement,
    TABLE_FREE_ELEMENT FreeElement,
    ULONG Unknown
);

ULONG NTAPI RtlNumberGenericTableElements( TABLE *pGenericTable );

BOOLEAN NTAPI RtlIsGenericTableEmpty( TABLE *pGenericTable );

PVOID NTAPI RtlGetElementGenericTable(
    TABLE *pGenericTable,
    ULONG ElementNumber
);

PVOID NTAPI RtlInsertElementGenericTable(
    TABLE *pGenericTable,
    PVOID ElementData,
    ULONG DataLength,
    OUT BOOLEAN *IsNewElement
);

PVOID NTAPI RtlLookupElementGenericTable(
    TABLE *pGenericTable,
    PVOID ElementToFind
);

BOOLEAN NTAPI RtlDeleteElementGenericTable(
    TABLE *pGenericTable,
    PVOID ElementToFind
);

 

int RtlLocateNodeGenericTable( TABLE *pTable, PVOID ElementToLocate, NODE **NodeFound );

UNKNOWN RtlRealInsertElementWorker( TABLE *pTable, PVOID ElementData, ULONG ElementSize, BOOLEAN *pResult OPTIONAL, NODE *pNode, ULONG SearchResult );

RtlInsertElementGenericTable
  RtlLocateNodeGenericTable
  RtlRealInsertElementWorker

RtlLookupElementGenericTable

RtlDeleteElementGenericTable

RtlGetElementGenericTable 함수의 소스코드 레벨 개선

PVOID stdcall MyRtlGetElementGenericTAble(TABLE *Table, ULONG ElementToGet)
{
 ULONG TotalElementCount = Table->NumberOfElements;
 LIST_ENTRY *ElementFound = Table->LastElementFound;
 ULONG LastIndexFound = Table->LastElementIndex;
 ULONG AdjustedElementToGet = ElementToGet+1;

 if (ElementToGet == -1 || AdjustedElementToGet > TotalElementCount)
  return 0;

 // 원하는 엔트리가 마지막으로 찾은 엔트리와 동일하면 반환한다.
 if (AdjustedElementToGet != LastIndexFound)
 {
  // LastIndexFound와 같지 않으면 계속 진행
  if (LastIndexFound > AdjustedElementToGet)
  {
   // 원하는 엔트리가 첫 번째 엔트리와 LastElementIndex 사이에
   // 존재하는 경우에 어느 방향으로 탐색해야 최대한 빨리 원하는
   // 엔트리에 도달하는지 결정한다.
   ULONG HalfWayFromLastFound = LastIndexFound / 2;
   if (AdjustedElementToGet > HalfwayFromLastFound)
   {
    // LastIndexFound부터 시작해서(원하는 엔트리가 LastIndexFound에
    // 더 가까이 존재하기 때문) 리스트의 시작부분으로 거꾸로 탐색한다.
    ULONG ElementsToGo = LastIndexFound - AdjustedElementToGet;
 
    while( ElementsToGo-- )
     ElementFound = ElementFound->Blink;
   }
   else
   {
    // 리스트의 첫 번째 엔트리부터 시작해서 앞으로 탐색을 시작한다.
    ULONG ElementsToGo = AdjustedElementToGet;
    ElementFound = (LIST_ENTRY *)&Table->LLHead;
 
    while(ElementsToGo--)
     ElementFound = ElementFound->Flink;
   }
  }
  else
  {
   // 원하는 엔트리의 인덱스가 LastElementIndex보다 큰 경우에
   // 원하는 엔트리가 리스트의 마지막 엔트리와 가까운지
   // LastElementIndex와 가까운지 결정한다.
   ULONG ElementsToLastFound = AdjustedElementToGet - LastIndexFound;
   ULONG ElementsToEnd = TotalElementCouint - AdjustedElementToGet + 1;

   if (ElementsToLastFound <= ElementsToEnd)
   {
    // 리스트의 마지막 엔트리보다 LastElementIndex에 더 가까운 경우에
    // LastElementIndex 부터 시작해서 앞으로 탐색한다.
    while (ElementsToLastFound--)
     ElementFound = ElementFound->Flink;
   }
   else
   {
    // 리스트의 마지막 엔트리에 더 가까운 경우에
    // 리스트의 헤드부터 시작해서 거꾸로 탐색한다.
    ElementFound = (LIST_ENTRY *)&Table->LLHead;
    while (ElementsToEnd--)
     ElementFound = ElementFound->Blink;
   }
  }

  // 다음 번 탐색을 위해서 찾은 엔트리를 저장해 놓는다.
  Table->LastElementFound = ElementFound;
  Table->LastElementIndex = AdJustedElementToGet;
 }

 // 엔트리의 헤드 부분이 아닌 데이터 부분을 반환한다.
 // 지금까지는 TABLE 데이터 구조체의 모든 내용을 다 알아낸 것이 아니므로
 // 단순히 ULONG 3개 크기만큼 증가시켰다.
 return (PVOID) ((PULONG) ElementFound + 3);
}

 

RtlInitializeGenericTable
RtlNumberGenericTableElements
RtlIsGenericTableEmpty
RtlGetElementGenericTable

지금까지 알아낸 TABLE 데이터 구조체의 내용
struct TABLE
{
    PVOID Unknown1;
    LIST_ENTRY *LLHead;
    LIST_ENTRY *SomeEntry;
    LIST_ENTRY *LastElementFound;
    ULONG LastElementIndex;
    ULONG NumberOfElements;
    ULONG Unknown1;
    ULONG Unknown2;
    ULONG Unknown3;
    ULONG Unknown4;
}