首页
论坛
课程
招聘
[讨论]有关句柄分配算法
2009-2-28 17:14 5375

[讨论]有关句柄分配算法

2009-2-28 17:14
5375
一直在想windows下的句柄是怎么进行分配和管理的
而这个句柄分配的算法又是windows不与公布的
在网上找了下 发现这方面的资料很少啊 于是自己对着WRK和reactOS看了一下午
虽然明白了一点点 但是还是有好多地方很迷糊 希望大牛们指导一下

从ExCreateHandle开始
到ExpAllocateHandleEntry
再到ExpAllocateHandleTableEntrySlow

定位句柄分配算法大概就位于此处

    if ( TableLevel == 0 ) {

        NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );

        if (NewMidLevel == NULL) {
            return FALSE;
        }

        NewMidLevel[1] = NewMidLevel[0];
        NewMidLevel[0] = (PHANDLE_TABLE_ENTRY)CapturedTable;

        CapturedTable = ((ULONG_PTR)NewMidLevel) | 1;
            
        OldValue = InterlockedExchangePointer( (PVOID *)&HandleTable->TableCode, (PVOID)CapturedTable );


    } else if (TableLevel == 1) {

        PHANDLE_TABLE_ENTRY *TableLevel2 = (PHANDLE_TABLE_ENTRY *)CapturedTable;

        i = HandleTable->NextHandleNeedingPool / (LOWLEVEL_COUNT * HANDLE_VALUE_INC);

        if (i < MIDLEVEL_COUNT) {
    
            NewLowLevel = ExpAllocateLowLevelTable( HandleTable, DoInit );

            if (NewLowLevel == NULL) {
                return FALSE;
            }

            OldValue = InterlockedExchangePointer( (PVOID *) (&TableLevel2[i]), NewLowLevel );
            EXASSERT (OldValue == NULL);

        } else {

            NewHighLevel = ExpAllocateTablePagedPool( HandleTable->QuotaProcess,
                                                      HIGHLEVEL_SIZE
                                                    );

            if (NewHighLevel == NULL) {

                return FALSE;
            }
                
            NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );

            if (NewMidLevel == NULL) {
                    
                ExpFreeTablePagedPool( HandleTable->QuotaProcess,
                                       NewHighLevel,
                                       HIGHLEVEL_SIZE
                                     );

                return FALSE;
            }

            NewHighLevel[0] = (PHANDLE_TABLE_ENTRY*)CapturedTable;
            NewHighLevel[1] = NewMidLevel;

            CapturedTable = ((ULONG_PTR)NewHighLevel) | 2;

            OldValue = InterlockedExchangePointer( (PVOID *)&HandleTable->TableCode, (PVOID)CapturedTable );

        }

    } else if (TableLevel == 2) {

        ULONG RemainingIndex;
        PHANDLE_TABLE_ENTRY **TableLevel3 = (PHANDLE_TABLE_ENTRY **)CapturedTable;

        i = HandleTable->NextHandleNeedingPool / (MIDLEVEL_THRESHOLD * HANDLE_VALUE_INC);

        if (i >= HIGHLEVEL_COUNT) {

            return FALSE;
        }

        if (TableLevel3[i] == NULL) {

            NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );
                
            if (NewMidLevel == NULL) {
                    
                return FALSE;
            }             

            OldValue = InterlockedExchangePointer( (PVOID *) &(TableLevel3[i]), NewMidLevel );
            EXASSERT (OldValue == NULL);

        } else {

            RemainingIndex = (HandleTable->NextHandleNeedingPool / HANDLE_VALUE_INC) -
                              i * MIDLEVEL_THRESHOLD;
            j = RemainingIndex / LOWLEVEL_COUNT;

            NewLowLevel = ExpAllocateLowLevelTable( HandleTable, DoInit );

            if (NewLowLevel == NULL) {

                return FALSE;
            }

            OldValue = InterlockedExchangePointer( (PVOID *)(&TableLevel3[i][j]) , NewLowLevel );
            EXASSERT (OldValue == NULL);
        }
    }


大致流程简化如下

if ( TableLevel == 0 ) 
{
    NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );
}
else if ( TableLevel == 1 )
{
    if (i < MIDLEVEL_COUNT)
    {
        NewLowLevel = ExpAllocateLowLevelTable( HandleTable, DoInit );
    }
    else
    {
        NewHighLevel = ExpAllocateTablePagedPool( HandleTable->QuotaProcess,
                                                      HIGHLEVEL_SIZE
                                                    );
        NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );
    }
}
else if (TableLevel == 2)
{
    if (i >= HIGHLEVEL_COUNT) 
            return FALSE;

    if (TableLevel3[i] == NULL)
         NewMidLevel = ExpAllocateMidLevelTable( HandleTable, DoInit, &NewLowLevel );
    else
        NewLowLevel = ExpAllocateLowLevelTable( HandleTable, DoInit );
}


思路可能是这样的 如果这一级句柄表满了以后就分配更高一级的句柄表,并修改HANDLE_TABLE结构中相应的部分使其指向高一级的句柄表 在高一级的句柄表中指向满掉的那个句柄表

这里有一个问题 当level=0时 并没有做任何判断 就用ExpAllocateMidLevelTable分配了一个中级表 这是为什么呢? 不是应该判断一下0级表有没有满吗?就像下面的都判断了i的值,这里为什么没有判断?

ps: 不知道有没有句柄算法的更详细的一点资料?

看雪论坛2020激励机制:能力值、活跃值和雪币体系!会员积分、权限和会员发帖、回帖活跃程度关联!

收藏
点赞0
打赏
分享
最新回复 (10)
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
eepo 活跃值 2009-3-1 02:02
2
0
顶起~ 期待解答
雪    币: 250
活跃值: 活跃值 (26)
能力值: ( LV12,RANK:450 )
在线值:
发帖
回帖
粉丝
weolar 活跃值 10 2009-3-1 10:07
3
0
这是我所找到的关于句柄的文章,你看看吧
上传的附件:
雪    币: 182
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
jinjing 活跃值 2009-3-1 13:00
4
0
有没有这种可能,就是在ExpAllocateMidLevelTable中做了判断了呢!
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
eepo 活跃值 2009-3-1 19:00
5
0
to weolar:
非常感谢你收集的这些资料。不过这些我大部分都看过,基本上都是关于句柄表和句柄的结构之类的,而很少有关于句柄分配的算法。

to jinjing:
我看了下ExpAllocateLowLevelTable和ExpAllocateMidLevelTable这两个函数
确切的说,我搞不懂这里LowLevel和MidLevel的含义 跟我们常讲的三层表有什么关系?
奇怪的是怎么没有HighLevel。。。

还望解答。
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
eepo 活跃值 2009-3-1 19:32
6
0
另外还有一个问题:
//
// Absolute maximum number of handles allowed
//
#define MAX_HANDLES (1<<24)


为什么最多句柄数是2^24个呢?
一级表1024个指针,指向二级表1024个指针,再指向三级表512个句柄表项
不是应该一共有1024*1024*512=2^29个吗?
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
eepo 活跃值 2009-3-2 13:50
7
0
仍然是不解~
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hongwater 活跃值 2009-3-2 18:56
8
0
ExpAllocateLowLevelTable这个函数其实就是分配一页(4k)来放HANDLE_TABLE_ENTRY结构,并初始化这页所有结构,最主要是用NextFreeTableEntry把所有结构连起来,所以分配的就是最Low那一层.但然如果你的句柄数不大于511的话,只这层就行了.

而ExpAllocateMidLevelTable分配的就是中间层了,它也是分配一页,它的每一项放的都是ExpAllocateLowLevelTable这个函数返回的地址。这个函数除了分配一个中间层以外,还用ExpAllocateLowLevelTable分配一个low层,并把这low层地址放到中间层第一项.

如果第一个中间层放不下句柄,那就要用到顶层.因为顶层只有一张表,所以它不需要像中间层和low层那么麻烦,所以直接用ExpAllocateTablePagedPool来分配就行了,它的每一项放的都是ExpAllocateMidLevelTable返回的地址.
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hongwater 活跃值 2009-3-2 18:58
9
0
你想一想分页池有多大,就明白了
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hongwater 活跃值 2009-3-2 19:15
10
0
它是在这个ExpAllocateHandleTableEntry函数里判断,通过HandleTable->FirstFree来判断,如果为0句柄表就是满了,否则它就是指向可获取的句柄的值.而这个HandleTable->FirstFree的值来源于NextFreeTableEntry,而NextFreeTableEntry初始化就看ExpAllocateLowLevelTable
雪    币: 215
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
eepo 活跃值 2009-3-3 16:03
11
0
to hongwater:非常感谢 我明白了!
游客
登录 | 注册 方可回帖
返回