00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
#include "cmp.h"
00031
00032
00033
00034
00035
HCELL_INDEX
00036
HvpDoAllocateCell(
00037
PHHIVE Hive,
00038 ULONG NewSize,
00039 HSTORAGE_TYPE Type
00040 );
00041
00042 ULONG
00043
HvpAllocateInBin(
00044
PHHIVE Hive,
00045
PHBIN Bin,
00046 ULONG Size,
00047 ULONG Type
00048 );
00049
00050 BOOLEAN
00051
HvpMakeBinPresent(
00052 IN
PHHIVE Hive,
00053 IN HCELL_INDEX Cell,
00054 IN
PHMAP_ENTRY Map
00055 );
00056
00057 BOOLEAN
00058
HvpIsFreeNeighbor(
00059
PHHIVE Hive,
00060
PHBIN Bin,
00061
PHCELL FreeCell,
00062
PHCELL *FreeNeighbor,
00063 HSTORAGE_TYPE Type
00064 );
00065
00066
VOID
00067
HvpDelistBinFreeCells(
00068
PHHIVE Hive,
00069
PHBIN Bin,
00070 HSTORAGE_TYPE Type,
00071 PHCELL_INDEX TailDisplay OPTIONAL
00072 );
00073
00074 #define CmpFindFirstSetRight KiFindFirstSetRight
00075 extern CCHAR
KiFindFirstSetRight[256];
00076 #define CmpFindFirstSetLeft KiFindFirstSetLeft
00077 extern CCHAR
KiFindFirstSetLeft[256];
00078
00079 #define HvpComputeIndex(Index, Size) \
00080
{ \
00081
Index = (Size >> HHIVE_FREE_DISPLAY_SHIFT) - 1; \
00082
if (Index >= HHIVE_LINEAR_INDEX ) { \
00083
\
00084
00085
00086
00087 \
00088 \
00089 if (Index > 255) { \
00090
00091
00092 \
00093 Index = HHIVE_FREE_DISPLAY_SIZE-1; \
00094 } else { \
00095 Index = CmpFindFirstSetLeft[Index] + \
00096 HHIVE_FREE_DISPLAY_BIAS; \
00097 } \
00098 } \
00099 }
00100
00101
#define ONE_K 1024
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
#define HvpAdjustCellSize(Size) \
00115
{ \
00116
ULONG onek = ONE_K; \
00117
ULONG Limit = 0; \
00118
\
00119
while( Size > onek ) { \
00120
onek<<=1; \
00121
Limit++; \
00122
} \
00123
\
00124
Size = Limit?onek:Size; \
00125
}
00126
00127
00128
#ifdef ALLOC_PRAGMA
00129
#pragma alloc_text(PAGE,HvpGetCellPaged)
00130
#pragma alloc_text(PAGE,HvpGetCellFlat)
00131
#pragma alloc_text(PAGE,HvpGetCellMap)
00132
#pragma alloc_text(PAGE,HvGetCellSize)
00133
#pragma alloc_text(PAGE,HvAllocateCell)
00134
#pragma alloc_text(PAGE,HvpDoAllocateCell)
00135
#pragma alloc_text(PAGE,HvFreeCell)
00136
#pragma alloc_text(PAGE,HvpIsFreeNeighbor)
00137
#pragma alloc_text(PAGE,HvpEnlistFreeCell)
00138
#pragma alloc_text(PAGE,HvpDelistFreeCell)
00139
#pragma alloc_text(PAGE,HvReallocateCell)
00140
#pragma alloc_text(PAGE,HvIsCellAllocated)
00141
#pragma alloc_text(PAGE,HvpAllocateInBin)
00142
#pragma alloc_text(PAGE,HvpMakeBinPresent)
00143
#pragma alloc_text(PAGE,HvpDelistBinFreeCells)
00144
#endif
00145
00146
00147
00148
00149
00150
struct _CELL_DATA *
00151
HvpGetCellPaged(
00152
PHHIVE Hive,
00153 HCELL_INDEX Cell
00154 )
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181 {
00182 ULONG Type;
00183 ULONG Table;
00184 ULONG Block;
00185 ULONG
Offset;
00186
PHCELL pcell;
00187
PHMAP_ENTRY Map;
00188
00189
CMLOG(
CML_FLOW,
CMS_MAP) {
00190 KdPrint((
"HvGetCellPaged:\n"));
00191 KdPrint((
"\tHive=%08lx Cell=%08lx\n",
Hive,
Cell));
00192 }
00193
ASSERT(
Hive->
Signature ==
HHIVE_SIGNATURE);
00194
ASSERT(
Cell !=
HCELL_NIL);
00195
ASSERT(
Hive->
Flat ==
FALSE);
00196
ASSERT((
Cell & (
HCELL_PAD(
Hive)-1))==0);
00197
ASSERT_CM_LOCK_OWNED();
00198
#if DBG
00199
if (
HvGetCellType(
Cell) ==
Stable) {
00200
ASSERT(
Cell >=
sizeof(
HBIN));
00201 }
else {
00202
ASSERT(
Cell >= (
HCELL_TYPE_MASK +
sizeof(
HBIN)));
00203 }
00204
#endif
00205
00206 Type =
HvGetCellType(
Cell);
00207 Table = (
Cell &
HCELL_TABLE_MASK) >>
HCELL_TABLE_SHIFT;
00208 Block = (
Cell &
HCELL_BLOCK_MASK) >>
HCELL_BLOCK_SHIFT;
00209
Offset = (
Cell &
HCELL_OFFSET_MASK);
00210
00211
ASSERT((
Cell - (Type *
HCELL_TYPE_MASK)) <
Hive->Storage[Type].Length);
00212
00213 Map = &((
Hive->Storage[Type].Map)->Directory[Table]->Table[Block]);
00214
ASSERT((Map->
BinAddress &
HMAP_BASE) != 0);
00215
ASSERT((Map->
BinAddress &
HMAP_DISCARDABLE) == 0);
00216 pcell = (
PHCELL)((ULONG_PTR)(Map->
BlockAddress) +
Offset);
00217
if (
USE_OLD_CELL(
Hive)) {
00218
return (
struct _CELL_DATA *)&(pcell->
u.OldCell.u.UserData);
00219 }
else {
00220
return (
struct _CELL_DATA *)&(pcell->
u.NewCell.u.UserData);
00221 }
00222 }
00223
00224
00225
struct _CELL_DATA *
00226
HvpGetCellFlat(
00227
PHHIVE Hive,
00228 HCELL_INDEX Cell
00229 )
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260 {
00261 PUCHAR base;
00262
PHCELL pcell;
00263
00264
CMLOG(
CML_FLOW,
CMS_MAP) {
00265 KdPrint((
"HvGetCellFlat:\n"));
00266 KdPrint((
"\tHive=%08lx Cell=%08lx\n",
Hive,
Cell));
00267 }
00268
ASSERT(
Hive->
Signature == HHIVE_SIGNATURE);
00269
ASSERT(Cell != HCELL_NIL);
00270
ASSERT(
Hive->
Flat == TRUE);
00271
ASSERT(
HvGetCellType(Cell) == Stable);
00272
ASSERT(Cell >=
sizeof(
HBIN));
00273
ASSERT(Cell < Hive->BaseBlock->Length);
00274
ASSERT((Cell & 0x7)==0);
00275
00276
00277
00278
00279 base = (PUCHAR)(
Hive->
BaseBlock) +
HBLOCK_SIZE;
00280 pcell = (
PHCELL)(base +
Cell);
00281
if (
USE_OLD_CELL(Hive)) {
00282
return (
struct _CELL_DATA *)&(pcell->
u.OldCell.u.UserData);
00283 }
else {
00284
return (
struct _CELL_DATA *)&(pcell->
u.NewCell.u.UserData);
00285 }
00286 }
00287
00288
00289
PHMAP_ENTRY
00290
HvpGetCellMap(
00291
PHHIVE Hive,
00292 HCELL_INDEX Cell
00293 )
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312 {
00313 ULONG Type;
00314 ULONG Table;
00315 ULONG Block;
00316
PHMAP_TABLE ptab;
00317
00318
CMLOG(
CML_FLOW,
CMS_MAP) {
00319 KdPrint((
"HvpGetCellMapPaged:\n"));
00320 KdPrint((
"\tHive=%08lx Cell=%08lx\n",
Hive,
Cell));
00321 }
00322
ASSERT(
Hive->
Signature == HHIVE_SIGNATURE);
00323
ASSERT(
Hive->
Flat == FALSE);
00324
ASSERT((Cell & (
HCELL_PAD(Hive)-1))==0);
00325
00326 Type =
HvGetCellType(Cell);
00327 Table = (
Cell &
HCELL_TABLE_MASK) >>
HCELL_TABLE_SHIFT;
00328 Block = (
Cell &
HCELL_BLOCK_MASK) >>
HCELL_BLOCK_SHIFT;
00329
00330
if ((
Cell - (Type *
HCELL_TYPE_MASK)) >=
Hive->Storage[Type].Length) {
00331
return NULL;
00332 }
00333
00334 ptab = (
Hive->Storage[Type].Map)->Directory[Table];
00335 return &(ptab->
Table[Block]);
00336 }
00337
00338
00339 LONG
00340
HvGetCellSize(
00341 IN
PHHIVE Hive,
00342 IN PVOID Address
00343 )
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 {
00371 LONG size;
00372
00373
CMLOG(
CML_FLOW,
CMS_MAP) {
00374 KdPrint((
"HvGetCellSize:\n"));
00375 KdPrint((
"\tAddress=%08lx\n", Address));
00376 }
00377
00378
if (
USE_OLD_CELL(Hive)) {
00379 size = ( (CONTAINING_RECORD(Address,
HCELL, u.OldCell.u.UserData))->Size ) * -1;
00380 size -= FIELD_OFFSET(
HCELL, u.OldCell.u.UserData);
00381 }
else {
00382 size = ( (CONTAINING_RECORD(Address,
HCELL, u.NewCell.u.UserData))->Size ) * -1;
00383 size -= FIELD_OFFSET(
HCELL, u.NewCell.u.UserData);
00384 }
00385
return size;
00386 }
00387
00388
00389
00390
HCELL_INDEX
00391
HvAllocateCell(
00392
PHHIVE Hive,
00393 ULONG NewSize,
00394 HSTORAGE_TYPE Type
00395 )
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416 {
00417
HCELL_INDEX NewCell;
00418
00419
CMLOG(
CML_MAJOR,
CMS_HIVE) {
00420 KdPrint((
"HvAllocateCell:\n"));
00421 KdPrint((
"\tHive=%08lx NewSize=%08lx\n",
Hive,NewSize));
00422 }
00423
ASSERT(
Hive->
Signature == HHIVE_SIGNATURE);
00424
ASSERT(
Hive->
ReadOnly == FALSE);
00425
ASSERT_CM_LOCK_OWNED_EXCLUSIVE();
00426
00427
00428
00429
00430
if (
USE_OLD_CELL(Hive)) {
00431 NewSize += FIELD_OFFSET(
HCELL, u.OldCell.u.UserData);
00432 }
else {
00433 NewSize += FIELD_OFFSET(
HCELL, u.NewCell.u.UserData);
00434 }
00435 NewSize =
ROUND_UP(NewSize,
HCELL_PAD(Hive));
00436
00437
00438
00439
00440
HvpAdjustCellSize(NewSize);
00441
00442
00443
00444
if (NewSize >
HSANE_CELL_MAX) {
00445
return HCELL_NIL;
00446 }
00447
00448
00449
00450
00451 NewCell =
HvpDoAllocateCell(Hive, NewSize, Type);
00452
00453
#if DBG
00454
if (NewCell !=
HCELL_NIL) {
00455
ASSERT(
HvIsCellAllocated(Hive, NewCell));
00456 }
00457
#endif
00458
00459
00460
CMLOG(CML_FLOW, CMS_HIVE) {
00461 KdPrint((
"\tNewCell=%08lx\n", NewCell));
00462 }
00463 return NewCell;
00464 }
00465
00466
00467
HCELL_INDEX
00468
HvpDoAllocateCell(
00469
PHHIVE Hive,
00470 ULONG NewSize,
00471 HSTORAGE_TYPE Type
00472 )
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493 {
00494 ULONG
Index;
00495 ULONG Summary;
00496
HCELL_INDEX cell;
00497
PHCELL pcell;
00498
HCELL_INDEX tcell;
00499
PHCELL ptcell;
00500
PHBIN Bin;
00501
PHMAP_ENTRY Me;
00502 ULONG offset;
00503
PHCELL next;
00504 ULONG MinFreeSize;
00505
00506
00507
CMLOG(
CML_MINOR,
CMS_HIVE) {
00508 KdPrint((
"HvDoAllocateCell:\n"));
00509 KdPrint((
"\tHive=%08lx NewSize=%08lx Type=%08lx\n",
Hive,NewSize,Type));
00510 }
00511
ASSERT(
Hive->
ReadOnly == FALSE);
00512
00513
00514
00515
00516
00517
HvpComputeIndex(Index, NewSize);
00518
00519
00520
00521
00522 Summary =
Hive->Storage[Type].FreeSummary;
00523 Summary = Summary & ~((1 <<
Index) - 1);
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
ASSERT(HHIVE_FREE_DISPLAY_SIZE == 24);
00534
while (Summary != 0) {
00535
if (Summary & 0xff) {
00536
Index =
CmpFindFirstSetRight[Summary & 0xff];
00537 }
else if (Summary & 0xff00) {
00538
Index =
CmpFindFirstSetRight[(Summary & 0xff00) >> 8] + 8;
00539 }
else {
00540
ASSERT(Summary & 0xff0000);
00541
Index =
CmpFindFirstSetRight[(Summary & 0xff0000) >> 16] + 16;
00542 }
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554 cell =
Hive->Storage[Type].FreeDisplay[
Index];
00555
while (cell !=
HCELL_NIL) {
00556
00557 pcell =
HvpGetHCell(Hive, cell);
00558
00559
if (NewSize <= (ULONG)pcell->
Size) {
00560
00561
00562
00563
00564
if (!
HvMarkCellDirty(Hive, cell)) {
00565
return HCELL_NIL;
00566 }
00567
00568
HvpDelistFreeCell(Hive, pcell, Type, NULL);
00569
00570
ASSERT(pcell->
Size > 0);
00571
ASSERT(NewSize <= (ULONG)pcell->Size);
00572
goto UseIt;
00573 }
00574
00575
if (
USE_OLD_CELL(Hive)) {
00576 cell = pcell->
u.OldCell.u.Next;
00577 }
else {
00578 cell = pcell->
u.NewCell.u.Next;
00579 }
00580
00581 }
00582
00583
00584
00585
00586
00587
00588
00589
ASSERT(Summary & (1 << Index));
00590 Summary = Summary & ~(1 <<
Index);
00591
00592 }
00593
00594
if (Summary == 0) {
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
if ((
Bin =
HvpAddBin(Hive, NewSize, Type)) !=
NULL) {
00608
00609
00610
00611
00612
DHvCheckBin(Hive,Bin);
00613 cell = (
Bin->
FileOffset) +
sizeof(
HBIN) + (Type*
HCELL_TYPE_MASK);
00614 pcell =
HvpGetHCell(Hive, cell);
00615 }
else {
00616
return HCELL_NIL;
00617 }
00618 }
00619
00620 UseIt:
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
ASSERT(pcell->
Size > 0);
00631
if (
USE_OLD_CELL(Hive)) {
00632 MinFreeSize = FIELD_OFFSET(
HCELL, u.OldCell.u.Next) +
sizeof(
HCELL_INDEX);
00633 }
else {
00634 MinFreeSize = FIELD_OFFSET(
HCELL, u.NewCell.u.Next) +
sizeof(
HCELL_INDEX);
00635 }
00636
if ((NewSize + MinFreeSize) < (ULONG)pcell->
Size) {
00637
00638
00639
00640
00641
00642 Me =
HvpGetCellMap(Hive, cell);
00643
VALIDATE_CELL_MAP(__LINE__,Me,Hive,cell);
00644
Bin = (
PHBIN)((Me->
BinAddress) &
HMAP_BASE);
00645 offset = (ULONG)((ULONG_PTR)pcell - (ULONG_PTR)
Bin);
00646
00647 ptcell = (
PHCELL)((PUCHAR)pcell + NewSize);
00648
if (
USE_OLD_CELL(Hive)) {
00649 ptcell->
u.OldCell.Last = offset;
00650 }
00651 ptcell->
Size = pcell->
Size - NewSize;
00652
00653
if ((offset + pcell->
Size) <
Bin->
Size) {
00654 next = (
PHCELL)((PUCHAR)pcell + pcell->
Size);
00655
if (
USE_OLD_CELL(Hive)) {
00656 next->
u.OldCell.Last = offset + NewSize;
00657 }
00658 }
00659
00660 pcell->
Size = NewSize;
00661 tcell = (
HCELL_INDEX)((ULONG)cell + NewSize);
00662
00663
HvpEnlistFreeCell(Hive, tcell, ptcell->
Size, Type, TRUE,NULL);
00664 }
00665
00666
00667
00668
00669
#if DBG
00670
if (
USE_OLD_CELL(Hive)) {
00671 RtlFillMemory(
00672 &(pcell->
u.OldCell.u.UserData),
00673 (pcell->
Size - FIELD_OFFSET(
HCELL, u.OldCell.u.UserData)),
00674 HCELL_ALLOCATE_FILL
00675 );
00676 }
else {
00677 RtlFillMemory(
00678 &(pcell->
u.NewCell.u.UserData),
00679 (pcell->
Size - FIELD_OFFSET(
HCELL, u.NewCell.u.UserData)),
00680 HCELL_ALLOCATE_FILL
00681 );
00682 }
00683
#endif
00684
pcell->
Size *= -1;
00685
00686
return cell;
00687 }
00688
00689
00690
00691
00692
VOID
00693
HvFreeCell(
00694
PHHIVE Hive,
00695 HCELL_INDEX Cell
00696 )
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721 {
00722
PHBIN Bin;
00723
PHCELL tmp;
00724
HCELL_INDEX newfreecell;
00725
PHCELL freebase;
00726 ULONG savesize;
00727
PHCELL neighbor;
00728 ULONG Type;
00729
PHMAP_ENTRY Me;
00730
00731
00732
CMLOG(
CML_MINOR,
CMS_HIVE) {
00733 KdPrint((
"HvFreeCell:\n"));
00734 KdPrint((
"\tHive=%08lx Cell=%08lx\n",
Hive,
Cell));
00735 }
00736
ASSERT(
Hive->
ReadOnly ==
FALSE);
00737
ASSERT_CM_LOCK_OWNED_EXCLUSIVE();
00738
00739
00740
00741
00742 Me =
HvpGetCellMap(
Hive,
Cell);
00743
VALIDATE_CELL_MAP(__LINE__,Me,
Hive,
Cell);
00744 Type =
HvGetCellType(
Cell);
00745
00746
Bin = (
PHBIN)((Me->
BinAddress) &
HMAP_BASE);
00747
DHvCheckBin(
Hive,
Bin);
00748
00749 freebase =
HvpGetHCell(
Hive,
Cell);
00750
00751
00752
00753
00754
ASSERT(freebase->
Size < 0);
00755 freebase->
Size *= -1;
00756
00757 savesize = freebase->
Size;
00758
00759
00760
00761
00762
00763
while (
00764
HvpIsFreeNeighbor(
00765
Hive,
00766
Bin,
00767 freebase,
00768 &neighbor,
00769 Type
00770 ) ==
TRUE
00771 )
00772 {
00773
00774
if (neighbor > freebase) {
00775
00776
00777
00778
00779
if (
USE_OLD_CELL(
Hive)) {
00780 tmp = (
PHCELL)((PUCHAR)neighbor + neighbor->
Size);
00781
if ( ((ULONG)((ULONG_PTR)tmp - (ULONG_PTR)
Bin)) <
Bin->
Size) {
00782 tmp->
u.OldCell.Last = (ULONG)((ULONG_PTR)freebase - (ULONG_PTR)
Bin);
00783 }
00784 }
00785 freebase->
Size += neighbor->
Size;
00786
00787 }
else {
00788
00789
00790
00791
00792
00793
if (
USE_OLD_CELL(
Hive)) {
00794 tmp = (
PHCELL)((PUCHAR)freebase + freebase->
Size);
00795
if ( ((ULONG)((ULONG_PTR)tmp - (ULONG_PTR)
Bin)) <
Bin->
Size ) {
00796 tmp->
u.OldCell.Last = (ULONG)((ULONG_PTR)neighbor - (ULONG_PTR)
Bin);
00797 }
00798 }
00799 neighbor->
Size += freebase->
Size;
00800 freebase = neighbor;
00801 }
00802 }
00803
00804
00805
00806
00807
00808 newfreecell = (
Bin->
FileOffset) +
00809 ((ULONG)((ULONG_PTR)freebase - (ULONG_PTR)
Bin)) +
00810 (Type*
HCELL_TYPE_MASK);
00811
00812
ASSERT(
HvpGetHCell(
Hive, newfreecell) == freebase);
00813
00814
#if DBG
00815
if (
USE_OLD_CELL(
Hive)) {
00816 RtlFillMemory(
00817 &(freebase->u.OldCell.u.UserData),
00818 (freebase->Size - FIELD_OFFSET(
HCELL, u.OldCell.u.UserData)),
00819
HCELL_FREE_FILL
00820 );
00821 }
else {
00822 RtlFillMemory(
00823 &(freebase->u.NewCell.u.UserData),
00824 (freebase->Size - FIELD_OFFSET(
HCELL, u.NewCell.u.UserData)),
00825
HCELL_FREE_FILL
00826 );
00827 }
00828
#endif
00829
00830
HvpEnlistFreeCell(
Hive, newfreecell, freebase->Size, Type,
TRUE,
NULL);
00831
00832 return;
00833 }
00834
00835
00836 BOOLEAN
00837
HvpIsFreeNeighbor(
00838
PHHIVE Hive,
00839
PHBIN Bin,
00840
PHCELL FreeCell,
00841
PHCELL *FreeNeighbor,
00842 HSTORAGE_TYPE Type
00843 )
00844
00845
00846
00847
00848
00849
00850
00851
00852
00853
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871 {
00872
PHCELL ptcell;
00873
00874
CMLOG(
CML_MINOR,
CMS_HIVE) {
00875 KdPrint((
"HvpIsFreeNeighbor:\n\tBin=%08lx",
Bin));
00876 KdPrint((
"FreeCell=%08lx\n", FreeCell));
00877 }
00878
ASSERT(
Hive->
ReadOnly == FALSE);
00879
00880
00881
00882
00883 *FreeNeighbor =
NULL;
00884 ptcell = (
PHCELL)((PUCHAR)FreeCell + FreeCell->
Size);
00885
ASSERT( ((ULONG)((ULONG_PTR)ptcell - (ULONG_PTR)Bin)) <=
Bin->
Size);
00886
if (((ULONG)((ULONG_PTR)ptcell - (ULONG_PTR)
Bin)) <
Bin->
Size) {
00887
if (ptcell->
Size > 0) {
00888 *FreeNeighbor = ptcell;
00889
goto FoundNeighbor;
00890 }
00891 }
00892
00893
00894
00895
00896
if (
USE_OLD_CELL(Hive)) {
00897
if (FreeCell->
u.OldCell.Last !=
HBIN_NIL) {
00898 ptcell = (
PHCELL)((PUCHAR)
Bin + FreeCell->
u.OldCell.Last);
00899
if (ptcell->
Size > 0) {
00900 *FreeNeighbor = ptcell;
00901
goto FoundNeighbor;
00902 }
00903 }
00904 }
else {
00905 ptcell = (
PHCELL)(
Bin+1);
00906
while (ptcell < FreeCell) {
00907
00908
00909
00910
00911
if (ptcell->
Size > 0) {
00912
00913
if ((
PHCELL)((PUCHAR)ptcell + ptcell->
Size) == FreeCell) {
00914 *FreeNeighbor = ptcell;
00915
00916
00917
00918
00919
00920
00921
00922
00923
00924
00925
00926
if ((Type ==
Volatile) ||
00927 (
HvMarkCellDirty(Hive, (ULONG)((ULONG_PTR)ptcell-(ULONG_PTR)Bin) +
Bin->
FileOffset))) {
00928
goto FoundNeighbor;
00929 }
else {
00930
return(
FALSE);
00931 }
00932
00933 }
else {
00934 ptcell = (
PHCELL)((PUCHAR)ptcell + ptcell->Size);
00935 }
00936 }
else {
00937 ptcell = (
PHCELL)((PUCHAR)ptcell - ptcell->Size);
00938 }
00939 }
00940 }
00941
00942
return(
FALSE);
00943
00944 FoundNeighbor:
00945
00946
HvpDelistFreeCell(Hive, *FreeNeighbor, Type, NULL);
00947 return TRUE;
00948 }
00949
00950
00951
VOID
00952
HvpEnlistFreeCell(
00953
PHHIVE Hive,
00954 HCELL_INDEX Cell,
00955 ULONG Size,
00956 HSTORAGE_TYPE Type,
00957 BOOLEAN CoalesceForward,
00958 PHCELL_INDEX TailDisplay OPTIONAL
00959 )
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986 {
00987
PHCELL_INDEX Last;
00988
PHCELL_INDEX First;
00989
PHMAP_ENTRY Map;
00990
PHCELL pcell;
00991
PHCELL pcellLast;
00992
PHCELL FirstCell;
00993 ULONG
Index;
00994
PHBIN Bin;
00995
HCELL_INDEX FreeCell;
00996
PFREE_HBIN FreeBin;
00997
PHBIN FirstBin;
00998
PHBIN LastBin;
00999
01000
HvpComputeIndex(
Index,
Size);
01001
01002
01003 First = &(
Hive->Storage[Type].FreeDisplay[
Index]);
01004 pcell =
HvpGetHCell(
Hive,
Cell);
01005
ASSERT(pcell->
Size > 0);
01006
ASSERT(
Size == (ULONG)pcell->
Size);
01007
01008
if (ARGUMENT_PRESENT(TailDisplay)) {
01009
01010
01011
01012 Last = &TailDisplay[
Index];
01013
if( *Last !=
HCELL_NIL ) {
01014
01015
01016
01017
01018 pcellLast =
HvpGetHCell(
Hive,*Last);
01019
ASSERT(pcellLast->
Size > 0);
01020
01021
if (
USE_OLD_CELL(
Hive)) {
01022 pcellLast->
u.OldCell.u.Next =
Cell;
01023 pcell->
u.OldCell.u.Next =
HCELL_NIL;
01024 }
else {
01025 pcellLast->
u.NewCell.u.Next =
Cell;
01026 pcell->
u.NewCell.u.Next =
HCELL_NIL;
01027 }
01028 }
else {
01029
01030
01031
01032
01033
ASSERT( *First ==
HCELL_NIL );
01034
01035
if (
USE_OLD_CELL(
Hive)) {
01036 pcell->
u.OldCell.u.Next = *First;
01037 }
else {
01038 pcell->
u.NewCell.u.Next = *First;
01039 }
01040 *First =
Cell;
01041 }
01042
01043
01044
01045 *Last =
Cell;
01046 }
else {
01047
01048
01049
01050
if (
USE_OLD_CELL(Hive)) {
01051 pcell->
u.OldCell.u.Next = *First;
01052 }
else {
01053 pcell->
u.NewCell.u.Next = *First;
01054 }
01055 *First =
Cell;
01056 }
01057
01058
01059
01060
01061
01062
01063 Map =
HvpGetCellMap(Hive, Cell);
01064
VALIDATE_CELL_MAP(__LINE__,Map,Hive,Cell);
01065
Bin = (
PHBIN)(Map->
BinAddress & ~
HMAP_NEWALLOC);
01066
if ((pcell == (
PHCELL)(
Bin + 1)) &&
01067 (
Size ==
Bin->
Size-
sizeof(
HBIN))) {
01068
01069
01070
01071
01072
01073
01074
01075
01076 FirstBin =
Bin;
01077
while (FirstBin->
MemAlloc == 0) {
01078 Map=
HvpGetCellMap(Hive,(FirstBin->
FileOffset - HBLOCK_SIZE) +
01079 (Type * HCELL_TYPE_MASK));
01080
VALIDATE_CELL_MAP(__LINE__,Map,Hive,(FirstBin->
FileOffset - HBLOCK_SIZE) +(Type * HCELL_TYPE_MASK));
01081 FirstBin = (
PHBIN)(Map->
BinAddress &
HMAP_BASE);
01082 FirstCell = (
PHCELL)(FirstBin+1);
01083
if ((ULONG)(FirstCell->
Size) != FirstBin->
Size-
sizeof(
HBIN)) {
01084
01085
01086
01087
01088
goto Done;
01089 }
01090 }
01091
01092
01093
01094
01095
01096
if (FirstBin->
FileOffset == 0) {
01097
goto Done;
01098 }
01099
01100 LastBin =
Bin;
01101
while (LastBin->
FileOffset+LastBin->
Size < FirstBin->
FileOffset+FirstBin->
MemAlloc) {
01102
if (!CoalesceForward) {
01103
01104
01105
01106
01107
goto Done;
01108 }
01109 Map =
HvpGetCellMap(Hive, (LastBin->
FileOffset+LastBin->
Size) +
01110 (Type * HCELL_TYPE_MASK));
01111
VALIDATE_CELL_MAP(__LINE__,Map,Hive,(LastBin->
FileOffset+LastBin->
Size) + (Type * HCELL_TYPE_MASK));
01112
01113
ASSERT(Map->
BinAddress != 0);
01114
01115 LastBin = (
PHBIN)(Map->
BinAddress &
HMAP_BASE);
01116 FirstCell = (
PHCELL)(LastBin + 1);
01117
if ((ULONG)(FirstCell->
Size) != LastBin->
Size-
sizeof(
HBIN)) {
01118
01119
01120
01121
01122
goto Done;
01123 }
01124 }
01125
01126
01127
01128
01129
01130
01131
if (FirstBin->
Size != FirstBin->
MemAlloc) {
01132
01133
01134
01135
01136
if (!
HvMarkDirty(Hive,
01137 FirstBin->
FileOffset + (Type * HCELL_TYPE_MASK),
01138
sizeof(
HBIN) +
sizeof(
HCELL))) {
01139
goto Done;
01140 }
01141
01142 }
01143
01144
01145 FreeBin = (
Hive->
Allocate)(
sizeof(
FREE_HBIN),
FALSE);
01146
if (FreeBin ==
NULL) {
01147
goto Done;
01148 }
01149
01150
01151
01152
01153
Bin = FirstBin;
01154
do {
01155 FirstCell = (
PHCELL)(
Bin+1);
01156
HvpDelistFreeCell(Hive, FirstCell, Type, TailDisplay);
01157
if (
Bin==LastBin) {
01158
break;
01159 }
01160 Map =
HvpGetCellMap(Hive, (
Bin->
FileOffset+
Bin->
Size)+
01161 (Type * HCELL_TYPE_MASK));
01162
VALIDATE_CELL_MAP(__LINE__,Map,Hive,(
Bin->
FileOffset+
Bin->
Size)+(Type * HCELL_TYPE_MASK));
01163
Bin = (
PHBIN)(Map->
BinAddress &
HMAP_BASE);
01164
01165 }
while (
TRUE );
01166
01167
01168
01169
01170 FirstBin->
Size = FirstBin->MemAlloc;
01171
01172 FreeBin->
Size = FirstBin->Size;
01173 FreeBin->
FileOffset = FirstBin->FileOffset;
01174 FirstCell = (
PHCELL)(FirstBin+1);
01175 FirstCell->
Size = FirstBin->Size -
sizeof(
HBIN);
01176
if (
USE_OLD_CELL(Hive)) {
01177 FirstCell->
u.OldCell.Last = (ULONG)
HBIN_NIL;
01178 }
01179
01180 InsertHeadList(&
Hive->Storage[Type].FreeBins, &FreeBin->
ListEntry);
01181
ASSERT_LISTENTRY(&FreeBin->
ListEntry);
01182
ASSERT_LISTENTRY(FreeBin->
ListEntry.Flink);
01183
01184 FreeCell = FirstBin->FileOffset+(Type*
HCELL_TYPE_MASK);
01185 FreeBin->
Flags =
FREE_HBIN_DISCARDABLE;
01186
while (FreeCell-FirstBin->FileOffset < FirstBin->Size) {
01187 Map =
HvpGetCellMap(Hive, FreeCell);
01188
VALIDATE_CELL_MAP(__LINE__,Map,Hive,FreeCell);
01189
if (Map->
BinAddress &
HMAP_NEWALLOC) {
01190 Map->
BinAddress = (ULONG_PTR)FirstBin |
HMAP_DISCARDABLE |
HMAP_NEWALLOC;
01191 }
else {
01192 Map->
BinAddress = (ULONG_PTR)FirstBin |
HMAP_DISCARDABLE;
01193 }
01194 Map->
BlockAddress = (ULONG_PTR)FreeBin;
01195 FreeCell +=
HBLOCK_SIZE;
01196 }
01197 }
01198
01199
01200 Done:
01201
Hive->Storage[Type].FreeSummary |= (1 <<
Index);
01202
return;
01203 }
01204
01205
01206
01207
VOID
01208
HvpDelistFreeCell(
01209
PHHIVE Hive,
01210
PHCELL Pcell,
01211 HSTORAGE_TYPE Type,
01212 PHCELL_INDEX TailDisplay OPTIONAL
01213 )
01214
01215
01216
01217
01218
01219
01220
01221
01222
01223
01224
01225
01226
01227
01228
01229
01230
01231
01232
01233
01234
01235 {
01236
PHCELL_INDEX List;
01237
HCELL_INDEX Prev =
HCELL_NIL;
01238 ULONG
Index;
01239
01240
HvpComputeIndex(
Index, Pcell->
Size);
01241
List = &(
Hive->Storage[Type].FreeDisplay[
Index]);
01242
01243
01244
01245
01246
ASSERT(*
List !=
HCELL_NIL);
01247
while (
HvpGetHCell(
Hive,*
List) != Pcell) {
01248 Prev = *
List;
01249
List = (
PHCELL_INDEX)
HvGetCell(
Hive,*
List);
01250
ASSERT(*
List !=
HCELL_NIL);
01251 }
01252
01253
if (ARGUMENT_PRESENT(TailDisplay)) {
01254
01255
01256
01257
if( *
List == TailDisplay[
Index] ) {
01258
01259
01260
01261
01262
#if DBG
01263
01264
01265
01266
if (
USE_OLD_CELL(Hive)) {
01267
ASSERT(Pcell->
u.OldCell.u.Next == HCELL_NIL);
01268 }
else {
01269
ASSERT(Pcell->
u.NewCell.u.Next == HCELL_NIL);
01270 }
01271
#endif
01272
01273 TailDisplay[
Index] = Prev;
01274 }
01275 }
01276
01277
01278
01279
01280
if (
USE_OLD_CELL(Hive)) {
01281 *
List = Pcell->
u.OldCell.u.Next;
01282 }
else {
01283 *
List = Pcell->
u.NewCell.u.Next;
01284 }
01285
01286
if (
Hive->Storage[Type].FreeDisplay[
Index] ==
HCELL_NIL) {
01287
01288
01289
01290
ASSERT(Prev == HCELL_NIL);
01291
01292
Hive->Storage[Type].FreeSummary &= ~(1 <<
Index);
01293 }
01294
01295 return;
01296 }
01297
01298
01299
HCELL_INDEX
01300
HvReallocateCell(
01301
PHHIVE Hive,
01302 HCELL_INDEX Cell,
01303 ULONG NewSize
01304 )
01305
01306
01307
01308
01309
01310
01311
01312
01313
01314
01315
01316
01317
01318
01319
01320
01321
01322
01323
01324
01325
01326
01327
01328
01329
01330
01331
01332
01333
01334
01335
01336
01337
01338
01339
01340
01341 {
01342 PUCHAR oldaddress;
01343 LONG oldsize;
01344 ULONG oldalloc;
01345
HCELL_INDEX NewCell;
01346 PUCHAR newaddress;
01347 ULONG Type;
01348
01349
CMLOG(
CML_MAJOR,
CMS_HIVE) {
01350 KdPrint((
"HvReallocateCell:\n"));
01351 KdPrint((
"\tHive=%08lx Cell=%08lx NewSize=%08lx\n",
Hive,
Cell,NewSize));
01352 }
01353
ASSERT(
Hive->
Signature == HHIVE_SIGNATURE);
01354
ASSERT(
Hive->
ReadOnly == FALSE);
01355
ASSERT_CM_LOCK_OWNED_EXCLUSIVE();
01356
01357
01358
01359
01360
if (
USE_OLD_CELL(Hive)) {
01361 NewSize += FIELD_OFFSET(
HCELL, u.OldCell.u.UserData);
01362 }
else {
01363 NewSize += FIELD_OFFSET(
HCELL, u.NewCell.u.UserData);
01364 }
01365 NewSize =
ROUND_UP(NewSize,
HCELL_PAD(Hive));
01366
01367
01368
01369
01370
HvpAdjustCellSize(NewSize);
01371
01372
01373
01374
01375
if (NewSize >
HSANE_CELL_MAX) {
01376
CMLOG(CML_FLOW, CMS_HIVE) {
01377 KdPrint((
"\tNewSize=%08lx\n", NewSize));
01378 }
01379
return HCELL_NIL;
01380 }
01381
01382
01383
01384
01385 oldaddress = (PUCHAR)
HvGetCell(Hive, Cell);
01386 oldsize =
HvGetCellSize(Hive, oldaddress);
01387
ASSERT(oldsize > 0);
01388
if (
USE_OLD_CELL(Hive)) {
01389 oldalloc = (ULONG)(oldsize + FIELD_OFFSET(
HCELL, u.OldCell.u.UserData));
01390 }
else {
01391 oldalloc = (ULONG)(oldsize + FIELD_OFFSET(
HCELL, u.NewCell.u.UserData));
01392 }
01393 Type =
HvGetCellType(Cell);
01394
01395
DHvCheckHive(Hive);
01396
01397
if (NewSize == oldalloc) {
01398
01399
01400
01401
01402 NewCell =
Cell;
01403
01404 }
else if (NewSize < oldalloc) {
01405
01406
01407
01408
01409
01410
01411 NewCell =
Cell;
01412
01413 }
else {
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
if ((NewCell =
HvpDoAllocateCell(Hive, NewSize, Type)) ==
HCELL_NIL) {
01430
return HCELL_NIL;
01431 }
01432
ASSERT(
HvIsCellAllocated(Hive, NewCell));
01433 newaddress = (PUCHAR)
HvGetCell(Hive, NewCell);
01434
01435
01436
01437
01438
01439 RtlMoveMemory(newaddress, oldaddress, oldsize);
01440
01441
01442
01443
01444
HvFreeCell(Hive, Cell);
01445 }
01446
01447
DHvCheckHive(Hive);
01448
return NewCell;
01449 }
01450
01451
01452
01453
01454
01455
01456
01457 BOOLEAN
01458
HvIsCellAllocated(
01459
PHHIVE Hive,
01460 HCELL_INDEX Cell
01461 )
01462
01463
01464
01465
01466
01467
01468
01469
01470
01471
01472
01473
01474
01475
01476
01477
01478
01479 {
01480 ULONG Type;
01481
PHCELL Address;
01482
PHCELL Below;
01483
PHMAP_ENTRY Me;
01484
PHBIN Bin;
01485 ULONG
Offset;
01486 LONG
Size;
01487
01488
01489
ASSERT(
Hive->
Signature ==
HHIVE_SIGNATURE);
01490
01491
if (
Hive->
Flat ==
TRUE) {
01492
return TRUE;
01493 }
01494
01495 Type =
HvGetCellType(
Cell);
01496
01497
if ( ((
Cell & ~
HCELL_TYPE_MASK) >
Hive->Storage[Type].Length) ||
01498 (
Cell %
HCELL_PAD(
Hive) != 0)
01499 )
01500 {
01501
return FALSE;
01502 }
01503
01504 Address =
HvpGetHCell(
Hive,
Cell);
01505 Me =
HvpGetCellMap(
Hive,
Cell);
01506
if (Me ==
NULL) {
01507
return FALSE;
01508 }
01509
Bin = (
PHBIN)((ULONG_PTR)(Me->
BinAddress) &
HMAP_BASE);
01510
Offset = (ULONG)((ULONG_PTR)Address - (ULONG_PTR)
Bin);
01511
Size = Address->
Size * -1;
01512
01513
if ( (Address->
Size > 0) ||
01514 ((
Offset + (ULONG)
Size) >
Bin->
Size) ||
01515 (
Offset <
sizeof(
HBIN))
01516 )
01517 {
01518
return FALSE;
01519 }
01520
01521
if (
USE_OLD_CELL(
Hive)) {
01522
if (Address->
u.OldCell.Last !=
HBIN_NIL) {
01523
01524
if (Address->
u.OldCell.Last >
Bin->
Size) {
01525
return FALSE;
01526 }
01527
01528 Below = (
PHCELL)((PUCHAR)
Bin + Address->
u.OldCell.Last);
01529
Size = (Below->
Size < 0) ?
01530 Below->
Size * -1 :
01531 Below->
Size;
01532
01533
if ( ((ULONG_PTR)Below +
Size) != (ULONG_PTR)Address ) {
01534
return FALSE;
01535 }
01536 }
01537 }
01538
01539
01540
return TRUE;
01541 }
01542
01543
VOID
01544
HvpDelistBinFreeCells(
01545
PHHIVE Hive,
01546
PHBIN Bin,
01547 HSTORAGE_TYPE Type,
01548 PHCELL_INDEX TailDisplay OPTIONAL
01549 )
01550
01551
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561
01562
01563
01564
01565
01566
01567
01568
01569
01570
01571
01572
01573 {
01574
PHCELL p;
01575 ULONG size;
01576
HCELL_INDEX Cell;
01577
PHMAP_ENTRY Map;
01578
PFREE_HBIN FreeBin;
01579 PLIST_ENTRY Entry;
01580
01581
Cell =
Bin->
FileOffset+(Type*
HCELL_TYPE_MASK);
01582 Map =
HvpGetCellMap(
Hive,
Cell);
01583
VALIDATE_CELL_MAP(__LINE__,Map,
Hive,
Cell);
01584
01585
01586
01587
01588
ASSERT( Map->
BinAddress == ((ULONG_PTR)
Bin |
HMAP_NEWALLOC) );
01589
01590
if( Map->
BinAddress &
HMAP_DISCARDABLE ) {
01591
01592
01593
01594
01595
01596
01597 Entry =
Hive->Storage[Type].FreeBins.Flink;
01598
while (Entry != &
Hive->Storage[Type].FreeBins) {
01599 FreeBin = CONTAINING_RECORD(Entry,
01600
FREE_HBIN,
01601 ListEntry);
01602
01603
01604
if( FreeBin->
FileOffset ==
Bin->
FileOffset ){
01605
01606
01607
01608
01609
01610
ASSERT( FreeBin->
Size ==
Bin->
Size );
01611
ASSERT_LISTENTRY(&FreeBin->
ListEntry);
01612
01613 RemoveEntryList(&FreeBin->
ListEntry);
01614 (
Hive->
Free)(FreeBin,
sizeof(
FREE_HBIN));
01615
return;
01616 }
01617
01618
01619 Entry = Entry->Flink;
01620 }
01621
01622
01623
CM_BUGCHECK(REGISTRY_ERROR,14,(ULONG)
Cell,(ULONG_PTR)Map,0);
01624
return;
01625 }
01626
01627
01628
01629
01630
01631 p = (
PHCELL)((PUCHAR)
Bin +
sizeof(
HBIN));
01632
01633
while (p < (
PHCELL)((PUCHAR)
Bin +
Bin->
Size)) {
01634
01635
01636
01637
01638
if (p->
Size >= 0) {
01639
01640 size = (ULONG)p->
Size;
01641
01642
01643
01644
01645
01646
HvpDelistFreeCell(Hive, p, Type, TailDisplay);
01647
01648 }
else {
01649
01650 size = (ULONG)(p->
Size * -1);
01651
01652 }
01653
01654
ASSERT(size >= 0);
01655 p = (
PHCELL)((PUCHAR)p + size);
01656 }
01657
01658
return;
01659 }