test: range.c Source File

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# range.c

Go to the documentation of this file.

    00001 /*++
    00002
    00003 Copyright (c) 1997  Microsoft Corporation
    00004
    00005 Module Name:
    00006
    00007     range.c
    00008
    00009 Abstract:
    00010
    00011     Kernel-mode range list support for arbiters
    00012
    00013 Author:
    00014
    00015     Andy Thornton (andrewth) 02/17/97
    00016
    00017 Revision History:
    00018
    00019 --*/
    00020
    00021 #include "ntrtlp.h"
    00022 #include "range.h"
    00023
    00024 #if DBG
    00025
    00026 //
    00027 // Debug print level:
    00028 //    -1 = no messages
    00029 //     0 = vital messages only
    00030 //     1 = call trace
    00031 //     2 = verbose messages
    00032 //
    00033
    00034 LONG RtlRangeDebugLevel = 0;
    00035
    00036 #endif
    00037
    00038 NTSTATUS
    00039 RtlpAddRange(
    00040     IN OUT PLIST_ENTRY ListHead,
    00041     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00042     IN ULONG AddRangeFlags
    00043     );
    00044
    00045 NTSTATUS
    00046 RtlpAddToMergedRange(
    00047     IN PRTLP_RANGE_LIST_ENTRY Merged,
    00048     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00049     IN ULONG AddRangeFlags
    00050     );
    00051
    00052 NTSTATUS
    00053 RtlpConvertToMergedRange(
    00054     IN PRTLP_RANGE_LIST_ENTRY Entry
    00055     );
    00056
    00057 PRTLP_RANGE_LIST_ENTRY
    00058 RtlpCreateRangeListEntry(
    00059     IN ULONGLONG Start,
    00060     IN ULONGLONG End,
    00061     IN UCHAR Attributes,
    00062     IN PVOID UserData,
    00063     IN PVOID Owner
    00064     );
    00065
    00066 NTSTATUS
    00067 RtlpAddIntersectingRanges(
    00068     IN PLIST_ENTRY ListHead,
    00069     IN PRTLP_RANGE_LIST_ENTRY First,
    00070     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00071     IN ULONG AddRangeFlags
    00072     );
    00073
    00074 NTSTATUS
    00075 RtlpDeleteFromMergedRange(
    00076     IN PRTLP_RANGE_LIST_ENTRY Delete,
    00077     IN PRTLP_RANGE_LIST_ENTRY Merged
    00078     );
    00079
    00080 PRTLP_RANGE_LIST_ENTRY
    00081 RtlpCopyRangeListEntry(
    00082     PRTLP_RANGE_LIST_ENTRY Entry
    00083     );
    00084
    00085 VOID
    00086 RtlpDeleteRangeListEntry(
    00087     IN PRTLP_RANGE_LIST_ENTRY Entry
    00088     );
    00089
    00090 BOOLEAN
    00091 RtlpIsRangeAvailable(
    00092     IN PRTL_RANGE_LIST_ITERATOR Iterator,
    00093     IN ULONGLONG Start,
    00094     IN ULONGLONG End,
    00095     IN UCHAR AttributeAvailableMask,
    00096     IN BOOLEAN SharedOK,
    00097     IN BOOLEAN NullConflictOK,
    00098     IN BOOLEAN Forward,
    00099     IN PVOID Context OPTIONAL,
    00100     IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL
    00101     );
    00102
    00103 #if DBG
    00104
    00105 VOID
    00106 RtlpDumpRangeListEntry(
    00107     LONG Level,
    00108     PRTLP_RANGE_LIST_ENTRY Entry,
    00109     BOOLEAN Indent
    00110     );
    00111
    00112 VOID
    00113 RtlpDumpRangeList(
    00114     LONG Level,
    00115     PRTL_RANGE_LIST RangeList
    00116     );
    00117
    00118 #else
    00119
    00120 #define RtlpDumpRangeListEntry(Level, Entry, Indent)
    00121 #define RtlpDumpRangeList(Level, RangeList)
    00122
    00123 #endif // DBG
    00124
    00125 //
    00126 // Make everything pageable or init
    00127 //
    00128
    00129 #ifdef ALLOC_PRAGMA
    00130
    00131 #if defined(NTOS_KERNEL_RUNTIME)
    00132 #pragma alloc_text(INIT, RtlInitializeRangeListPackage)
    00133 #endif
    00134
    00135 #pragma alloc_text(PAGE, RtlpAddRange)
    00136 #pragma alloc_text(PAGE, RtlpAddToMergedRange)
    00137 #pragma alloc_text(PAGE, RtlpConvertToMergedRange)
    00138 #pragma alloc_text(PAGE, RtlpCreateRangeListEntry)
    00139 #pragma alloc_text(PAGE, RtlpAddIntersectingRanges)
    00140 #pragma alloc_text(PAGE, RtlpDeleteFromMergedRange)
    00141 #pragma alloc_text(PAGE, RtlpCopyRangeListEntry)
    00142 #pragma alloc_text(PAGE, RtlpDeleteRangeListEntry)
    00143 #pragma alloc_text(PAGE, RtlpIsRangeAvailable)
    00144
    00145 #if DBG
    00146 #pragma alloc_text(PAGE, RtlpDumpRangeListEntry)
    00147 #pragma alloc_text(PAGE, RtlpDumpRangeList)
    00148 #endif
    00149
    00150 #pragma alloc_text(PAGE, RtlInitializeRangeList)
    00151 #pragma alloc_text(PAGE, RtlAddRange)
    00152 #pragma alloc_text(PAGE, RtlDeleteRange)
    00153 #pragma alloc_text(PAGE, RtlDeleteOwnersRanges)
    00154 #pragma alloc_text(PAGE, RtlCopyRangeList)
    00155 #pragma alloc_text(PAGE, RtlFreeRangeList)
    00156 #pragma alloc_text(PAGE, RtlIsRangeAvailable)
    00157 #pragma alloc_text(PAGE, RtlFindRange)
    00158 #pragma alloc_text(PAGE, RtlGetFirstRange)
    00159 #pragma alloc_text(PAGE, RtlGetNextRange)
    00160 #pragma alloc_text(PAGE, RtlMergeRangeLists)
    00161 #pragma alloc_text(PAGE, RtlInvertRangeList)
    00162
    00163 #endif // ALLOC_PRAGMA
    00164
    00165 //
    00166 // Range List memory allocation
    00167 //
    00168
    00169 #if defined(NTOS_KERNEL_RUNTIME)
    00170
    00171 //
    00172 // The kernel mode range list API uses a lookaside list to speed allocation
    00173 // of range list entries.  The PAGED_LOOKASIDE_LIST structure should be non-paged.
    00174 //
    00175
    00176 #define RTLP_RANGE_LIST_ENTRY_LOOKASIDE_DEPTH   16
    00177
    00178 PAGED_LOOKASIDE_LIST RtlpRangeListEntryLookasideList;
    00179
    00180 VOID
    00181 RtlInitializeRangeListPackage(
    00182     VOID
    00183     )
    00184 /*++
    00185
    00186 Routine Description:
    00187
    00188     This routine initializes the stuctures required by the range list
    00189     APIs.  It is called during system initialization (Phase1Initialization)
    00190     and should be before any of the range list apis are called.
    00191
    00192 Arguments:
    00193
    00194     None.
    00195
    00196 Return Value:
    00197
    00198     None.
    00199
    00200 --*/
    00201 {
    00202     ExInitializePagedLookasideList(
    00203         &RtlpRangeListEntryLookasideList,
    00204         NULL,
    00205         NULL,
    00206         0,
    00207         sizeof(RTLP_RANGE_LIST_ENTRY),
    00208         RTL_RANGE_LIST_ENTRY_TAG,
    00209         RTLP_RANGE_LIST_ENTRY_LOOKASIDE_DEPTH
    00210         );
    00211
    00212 }
    00213
    00214 //
    00215 // PRANGE_LIST_ENTRY
    00216 // RtlpAllocateRangeListEntry(
    00217 //     VOID
    00218 //     )
    00219 //
    00220 #define RtlpAllocateRangeListEntry()                                    \
    00221     (PRTLP_RANGE_LIST_ENTRY) ExAllocateFromPagedLookasideList(          \
    00222         &RtlpRangeListEntryLookasideList                                \
    00223         )
    00224
    00225 //
    00226 // VOID
    00227 // RtlpFreeRangeListEntry(
    00228 //     IN PRTLP_RANGE_LIST_ENTRY Entry
    00229 //     )
    00230 //
    00231 #define RtlpFreeRangeListEntry(Entry)                                   \
    00232     ExFreeToPagedLookasideList(&RtlpRangeListEntryLookasideList, (Entry))
    00233
    00234
    00235 //
    00236 // PVOID
    00237 // RtlpRangeListAllocatePool(
    00238 //     IN ULONG Size
    00239 //     )
    00240 //
    00241 #define RtlpRangeListAllocatePool(Size)                                 \
    00242     ExAllocatePoolWithTag(PagedPool, (Size), RTL_RANGE_LIST_MISC_TAG)
    00243
    00244 //
    00245 // VOID
    00246 // RtlpRangeListFreePool(
    00247 //     IN PVOID Free
    00248 //     )
    00249 //
    00250 #define RtlpRangeListFreePool(Free)                                     \
    00251     ExFreePool(Free)
    00252
    00253
    00254 #else // defined(NTOS_KERNEL_RUNTIME)
    00255
    00256
    00257 //
    00258 // Usermode range lists use the standard Rtl heap for allocations
    00259 //
    00260
    00261 //
    00262 // PRANGE_LIST_ENTRY
    00263 // RtlpAllocateRangeListEntry(
    00264 //     VOID
    00265 //     );
    00266 //
    00267 #define RtlpAllocateRangeListEntry()                                    \
    00268     (PRTLP_RANGE_LIST_ENTRY) RtlAllocateHeap(                           \
    00269         RtlProcessHeap(),                                               \
    00270         RTL_RANGE_LIST_ENTRY_TAG,                                       \
    00271         sizeof(RTLP_RANGE_LIST_ENTRY)                                   \
    00272         )
    00273
    00274 //
    00275 // VOID
    00276 // RtlpFreeRangeListEntry(
    00277 //     IN PRTLP_RANGE_LIST_ENTRY Entry
    00278 //     )
    00279 //
    00280 #define RtlpFreeRangeListEntry(Entry)                                   \
    00281     RtlFreeHeap( RtlProcessHeap(), 0, (Entry) )
    00282
    00283 //
    00284 // PVOID
    00285 // RtlpRangeListAllocatePool(
    00286 //     IN ULONG Size
    00287 //     )
    00288 //
    00289 #define RtlpRangeListAllocatePool(Size)                                 \
    00290     RtlAllocateHeap(RtlProcessHeap(), RTL_RANGE_LIST_MISC_TAG, (Size))
    00291
    00292 //
    00293 // VOID
    00294 // RtlpRangeListFreePool(
    00295 //     IN PVOID Free
    00296 //     )
    00297 //
    00298 #define RtlpRangeListFreePool(Free)                                     \
    00299     RtlFreeHeap( RtlProcessHeap(), 0, (Free) )
    00300
    00301
    00302 #endif // defined(NTOS_KERNEL_RUNTIME)
    00303
    00304 VOID
    00305 RtlInitializeRangeList(
    00306     IN OUT PRTL_RANGE_LIST RangeList
    00307     )
    00308 /*++
    00309
    00310 Routine Description:
    00311
    00312     This routine initializes a range list.  It must be called before the range
    00313     list is passed to any of the other range list functions.  Initially the
    00314     range list contains no ranges
    00315
    00316 Arguments:
    00317
    00318     RangeList - Pointer to a user allocated RTL_RANGE_LIST structre to be
    00319         initialized.
    00320
    00321 Return Value:
    00322
    00323     None.
    00324
    00325 --*/
    00326 {
    00327     RTL_PAGED_CODE();
    00328
    00329     ASSERT(RangeList);
    00330
    00331     DEBUG_PRINT(1, ("RtlInitializeRangeList(0x%08x)\n", RangeList));
    00332
    00333     InitializeListHead(&RangeList->ListHead);
    00334     RangeList->Flags = 0;
    00335     RangeList->Count = 0;
    00336     RangeList->Stamp = 0;
    00337 }
    00338
    00339 NTSTATUS
    00340 RtlAddRange(
    00341     IN OUT PRTL_RANGE_LIST RangeList,
    00342     IN ULONGLONG Start,
    00343     IN ULONGLONG End,
    00344     IN UCHAR Attributes,
    00345     IN ULONG Flags,
    00346     IN PVOID UserData, OPTIONAL
    00347     IN PVOID Owner     OPTIONAL
    00348     )
    00349 /*++
    00350
    00351 Routine Description:
    00352
    00353     This routine adds a new range with the specified properties to a range list.
    00354
    00355 Arguments:
    00356
    00357     RangeList - Pointer to the range list to which the new range is to be added.
    00358         It must have been previously initialized using RtlInitializeRangeList.
    00359
    00360     Start - The location of the start of the new range.
    00361
    00362     End - The location of the end of the new range.
    00363
    00364     Flags - These determine the range's properties and how it is added:
    00365
    00366         RTL_RANGE_LIST_ADD_IF_CONFLICT - The range should be added even if it
    00367             overlaps another range.  In this case the RTL_RANGE_CONFLICT flag
    00368             is set.
    00369
    00370         RTL_RANGE_LIST_ADD_SHARED - The range is marked as an RTL_RANGE_SHARED
    00371             and will successfully be added if it overlaps another shared range.
    00372             It can be speficied in conjunction with the above ADD_IF_CONFLICT
    00373             flag in which case if the range overlaps a non-shared range it will
    00374             be marked as both RTL_RANGE_SHARED and RTL_RANGE_CONFLICT.
    00375
    00376     UserData - Extra data to be stored with the range.  The system will not
    00377         attempt to interpret it.
    00378
    00379     Owner - A cookie that represents the entity that owns this range.  (A
    00380         pointer to some object is the most likley).  The system will not
    00381         attempt to interpret it, just use it to distinguish the range from
    00382         another with the same start and end.
    00383
    00384 Return Value:
    00385
    00386     Status code that indicates whether or not the function was successful:
    00387
    00388     STATUS_INVALID_PARAMETER
    00389     STATUS_RANGE_LIST_CONFLICT
    00390     STATUS_INSUFFICIENT_RESOURCES
    00391
    00392 --*/
    00393 {
    00394
    00395     NTSTATUS status;
    00396     PRTLP_RANGE_LIST_ENTRY newEntry = NULL;
    00397
    00398     RTL_PAGED_CODE();
    00399
    00400     DEBUG_PRINT(1,
    00401         ("RtlAddRange(0x%08x, 0x%I64x, 0x%I64x, 0x%08x, 0x%08x, 0x%08x)\n",
    00402         RangeList,
    00403         Start,
    00404         End,
    00405         Flags,
    00406         UserData,
    00407         Owner
    00408         ));
    00409
    00410     //
    00411     // Validate parameters
    00412     //
    00413
    00414     if (End < Start) {
    00415         return STATUS_INVALID_PARAMETER;
    00416     }
    00417
    00418     //
    00419     // Create a new entry
    00420     //
    00421
    00422     if (!(newEntry = RtlpCreateRangeListEntry(Start, End, Attributes, UserData, Owner))) {
    00423         return STATUS_INSUFFICIENT_RESOURCES;
    00424     }
    00425
    00426     //
    00427     // Mark the new entry as shared if appropriate
    00428     //
    00429
    00430     if (Flags & RTL_RANGE_LIST_ADD_SHARED) {
    00431         newEntry->PublicFlags |= RTL_RANGE_SHARED;
    00432     }
    00433
    00434     status = RtlpAddRange(&RangeList->ListHead,
    00435                         newEntry,
    00436                         Flags
    00437                         );
    00438
    00439     if (NT_SUCCESS(status)) {
    00440
    00441         //
    00442         // We added a range so bump the count
    00443         //
    00444         RangeList->Count++;
    00445         RangeList->Stamp++;
    00446
    00447     } else {
    00448
    00449         //
    00450         // We didn't add a range so free up the entry
    00451         //
    00452
    00453         RtlpFreeRangeListEntry(newEntry);
    00454     }
    00455
    00456     return status;
    00457
    00458 }
    00459
    00460 NTSTATUS
    00461 RtlpAddRange(
    00462     IN OUT PLIST_ENTRY ListHead,
    00463     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00464     IN ULONG AddRangeFlags
    00465     )
    00466 /*++
    00467
    00468 Routine Description:
    00469
    00470     This routine implement the AddRange operation adding the range in the
    00471     appropriate place in the sorted range list, converting ranges to merged
    00472     ranges and setting RTL_RANGE_CONFLICT flags as necessary.
    00473
    00474 Arguments:
    00475
    00476     ListHead - The list of the range list to which the range should be added.
    00477
    00478     Entry - The new entry to be added to the range list
    00479
    00480     AddRangeFlags - The Flags argument to RtlAddRange, see above.
    00481
    00482 Return Value:
    00483
    00484     Status code that indicates whether or not the function was successful:
    00485
    00486     STATUS_RANGE_LIST_CONFLICT
    00487     STATUS_INSUFFICIENT_RESOURCES
    00488
    00489 --*/
    00490 {
    00491     NTSTATUS status = STATUS_SUCCESS;
    00492     PRTLP_RANGE_LIST_ENTRY previous, current;
    00493     ULONGLONG start, end;
    00494
    00495     DEBUG_PRINT(2,
    00496                 ("RtlpAddRange(0x%08x, 0x%08x{0x%I64x-0x%I64x}, 0x%08x)\n",
    00497                 ListHead,
    00498                 Entry,
    00499                 Entry->Start,
    00500                 Entry->End,
    00501                 AddRangeFlags
    00502                 ));
    00503
    00504     RTL_PAGED_CODE();
    00505     ASSERT(Entry);
    00506
    00507     start = Entry->Start;
    00508     end = Entry->End;
    00509
    00510     //
    00511     // Clear the conflict flag if it was left around
    00512     //
    00513
    00514     Entry->PublicFlags &= ~RTL_RANGE_CONFLICT;
    00515
    00516     //
    00517     // Iterate through the list and find where to insert the entry
    00518     //
    00519
    00520     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY, ListHead, current) {
    00521
    00522         if (end < current->Start) {
    00523
    00524             //
    00525             // The new range is completely before this one
    00526             //
    00527
    00528             DEBUG_PRINT(2, ("Completely before\n"));
    00529
    00530             InsertEntryList(current->ListEntry.Blink,
    00531                             &Entry->ListEntry
    00532                             );
    00533
    00534             goto exit;
    00535
    00536         } else if (RANGE_INTERSECT(Entry, current)) {
    00537
    00538             status = RtlpAddIntersectingRanges(ListHead,
    00539                        current,
    00540                        Entry,
    00541                        AddRangeFlags);
    00542
    00543             goto exit;
    00544
    00545         }
    00546     }
    00547
    00548     //
    00549     // New range is after all existing ranges
    00550     //
    00551
    00552     DEBUG_PRINT(2, ("After all existing ranges\n"));
    00553
    00554     InsertTailList(ListHead,
    00555                    &Entry->ListEntry
    00556                   );
    00557
    00558 exit:
    00559
    00560     return status;
    00561
    00562 }
    00563
    00564 NTSTATUS
    00565 RtlpAddToMergedRange(
    00566     IN PRTLP_RANGE_LIST_ENTRY Merged,
    00567     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00568     IN ULONG AddRangeFlags
    00569     )
    00570 /*++
    00571
    00572 Routine Description:
    00573
    00574     This routine adds a new range to a merged range, setting the
    00575     RTL_RANGE_CONFLICT flags if necessary.
    00576
    00577 Arguments:
    00578
    00579     Merged - The merged range to which Entry should be added.
    00580
    00581     Entry - The new entry to be added to the range list
    00582
    00583     AddRangeFlags - The Flags argument to RtlAddRange, see above.
    00584
    00585 Return Value:
    00586
    00587     Status code that indicates whether or not the function was successful:
    00588
    00589     STATUS_RANGE_LIST_CONFLICT - indictates that the range was not added because
    00590         it conflicted with another range and conflicts are not allowed
    00591
    00592 --*/
    00593 {
    00594     PRTLP_RANGE_LIST_ENTRY current;
    00595     PLIST_ENTRY insert = NULL;
    00596     BOOLEAN entryShared;
    00597
    00598     RTL_PAGED_CODE();
    00599     ASSERT(Merged);
    00600     ASSERT(Entry);
    00601     ASSERT(MERGED(Merged));
    00602
    00603     entryShared = SHARED(Entry);
    00604
    00605     //
    00606     // Insert it into the merged list, this is sorted in order of start
    00607     //
    00608
    00609     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY, &Merged->Merged.ListHead, current) {
    00610
    00611         //
    00612         // Do we conflict?
    00613         //
    00614
    00615         if (RANGE_INTERSECT(current, Entry)
    00616         && !(entryShared && SHARED(current))) {
    00617
    00618             //
    00619             // Are conflicts ok?
    00620             //
    00621
    00622             if (AddRangeFlags & RTL_RANGE_LIST_ADD_IF_CONFLICT) {
    00623
    00624                 //
    00625                 // Yes - Mark both entries as conflicting
    00626                 //
    00627
    00628                 current->PublicFlags |= RTL_RANGE_CONFLICT;
    00629                 Entry->PublicFlags |= RTL_RANGE_CONFLICT;
    00630
    00631             } else {
    00632
    00633                 //
    00634                 // No - Fail
    00635                 //
    00636
    00637                 return STATUS_RANGE_LIST_CONFLICT;
    00638
    00639             }
    00640         }
    00641
    00642         //
    00643         // Have we not yet found the insertion point and just passed it?
    00644         //
    00645
    00646         if (!insert && current->Start > Entry->Start) {
    00647
    00648             //
    00649             // Insert is before current
    00650             //
    00651
    00652             insert = current->ListEntry.Blink;
    00653         }
    00654     }
    00655
    00656     //
    00657     // Did we find where to insert the new range?
    00658     //
    00659
    00660     if (!insert) {
    00661
    00662         //
    00663         // New range is after all existing ranges
    00664         //
    00665
    00666         InsertTailList(&Merged->Merged.ListHead,
    00667                        &Entry->ListEntry
    00668                       );
    00669
    00670     } else {
    00671
    00672         //
    00673         // Insert in the list
    00674         //
    00675
    00676         InsertEntryList(insert,
    00677                         &Entry->ListEntry
    00678                         );
    00679     }
    00680
    00681
    00682     //
    00683     // Expand the merged range if necessary
    00684     //
    00685
    00686     if (Entry->Start < Merged->Start) {
    00687         Merged->Start = Entry->Start;
    00688     }
    00689
    00690     if (Entry->End > Merged->End) {
    00691         Merged->End = Entry->End;
    00692     }
    00693
    00694     //
    00695     // If we just added a shared range to a completely shared merged
    00696     // range then the shared flag can stay otherwise it must go
    00697     //
    00698
    00699     if (SHARED(Merged) && !entryShared) {
    00700
    00701         DEBUG_PRINT(2,
    00702             ("RtlpAddToMergedRange: Merged range no longer completely shared\n"));
    00703
    00704         Merged->PublicFlags &= ~RTL_RANGE_SHARED;
    00705     }
    00706
    00707     return STATUS_SUCCESS;
    00708 }
    00709
    00710 NTSTATUS
    00711 RtlpConvertToMergedRange(
    00712     IN PRTLP_RANGE_LIST_ENTRY Entry
    00713     )
    00714 /*++
    00715
    00716 Routine Description:
    00717
    00718     This converts a non-merged range into a merged range with one member, the
    00719     range that was just converted.
    00720
    00721 Arguments:
    00722
    00723     Entry - The entry to be converted into a merged range.
    00724
    00725 Return Value:
    00726
    00727     Status code that indicates whether or not the function was successful:
    00728
    00729     STATUS_INSUFFICIENT_RESOURCES
    00730
    00731 --*/
    00732 {
    00733     PRTLP_RANGE_LIST_ENTRY newEntry;
    00734
    00735     RTL_PAGED_CODE();
    00736     ASSERT(Entry);
    00737     ASSERT(!MERGED(Entry));
    00738     ASSERT(!CONFLICT(Entry));
    00739
    00740     //
    00741     // Create a new entry
    00742     //
    00743
    00744     if (!(newEntry = RtlpCopyRangeListEntry(Entry))) {
    00745         return STATUS_INSUFFICIENT_RESOURCES;
    00746     }
    00747
    00748     //
    00749     // Convert the current entry into a merged one NB. Throw away all the
    00750     // private flags but leave the public ones as they can only be shared.
    00751     //
    00752
    00753     InitializeListHead(&Entry->Merged.ListHead);
    00754     Entry->PrivateFlags = RTLP_RANGE_LIST_ENTRY_MERGED;
    00755
    00756     ASSERT(Entry->PublicFlags == RTL_RANGE_SHARED || Entry->PublicFlags == 0);
    00757
    00758     //
    00759     // Add the range
    00760     //
    00761
    00762     InsertHeadList(&Entry->Merged.ListHead,
    00763                    &newEntry->ListEntry
    00764                    );
    00765
    00766
    00767     return STATUS_SUCCESS;
    00768 }
    00769
    00770 PRTLP_RANGE_LIST_ENTRY
    00771 RtlpCreateRangeListEntry(
    00772     IN ULONGLONG Start,
    00773     IN ULONGLONG End,
    00774     IN UCHAR Attributes,
    00775     IN PVOID UserData,
    00776     IN PVOID Owner
    00777     )
    00778 /*++
    00779
    00780 Routine Description:
    00781
    00782     This routine allocates a new range list entry and fills it in the the data
    00783     provided.
    00784
    00785 Arguments:
    00786
    00787     Start - The location of the start of the new range.
    00788
    00789     End - The location of the end of the new range.
    00790
    00791     Attributes - Extra data (normally flags) to be stored with the range. The
    00792         system will not attempt to interpret it.
    00793
    00794     UserData - Extra data to be stored with the range.  The system will not
    00795         attempt to interpret it.
    00796
    00797     Owner - A cookie that represents the entity that owns this range.  (A
    00798         pointer to some object is the most likley).  The system will not
    00799         attempt to interpret it, just use it to distinguish the range from
    00800         another with the same start and end.
    00801
    00802 Return Value:
    00803
    00804     Pointer to the new range list entry or NULL if a new entry could not be
    00805     allocated.
    00806
    00807 --*/
    00808 {
    00809     PRTLP_RANGE_LIST_ENTRY entry;
    00810
    00811     RTL_PAGED_CODE();
    00812     ASSERT(Start <= End);
    00813
    00814     //
    00815     // Allocate a new entry
    00816     //
    00817
    00818     if (entry = RtlpAllocateRangeListEntry()) {
    00819
    00820         //
    00821         // Fill in the details
    00822         //
    00823
    00824 #if DBG
    00825         entry->ListEntry.Flink = NULL;
    00826         entry->ListEntry.Blink = NULL;
    00827 #endif
    00828
    00829         entry->PublicFlags = 0;
    00830         entry->PrivateFlags = 0;
    00831         entry->Start = Start;
    00832         entry->End = End;
    00833         entry->Allocated.UserData = UserData;
    00834         entry->Allocated.Owner = Owner;
    00835         entry->Attributes = Attributes;
    00836     }
    00837
    00838     return entry;
    00839
    00840 }
    00841
    00842 NTSTATUS
    00843 RtlpAddIntersectingRanges(
    00844     IN PLIST_ENTRY ListHead,
    00845     IN PRTLP_RANGE_LIST_ENTRY First,
    00846     IN PRTLP_RANGE_LIST_ENTRY Entry,
    00847     IN ULONG AddRangeFlags
    00848     )
    00849 /*++
    00850
    00851 Routine Description:
    00852
    00853     This routine adds a range to a range list when the new range overlaps
    00854     an existing range.  Ranges are converted to mergedranges and the
    00855     RTL_RANGE_CONFLICT flag is set as necessary.
    00856
    00857 Arguments:
    00858
    00859     ListHead - The list of the range list to which the range should be added.
    00860
    00861     First - The first range that intersects
    00862
    00863     Entry - The new range to be added
    00864
    00865     AddRangeFlags - The Flags argument to RtlAddRange, see above.
    00866
    00867 Return Value:
    00868
    00869     Status code that indicates whether or not the function was successful:
    00870
    00871     STATUS_INSUFFICIENT_RESOURCES
    00872     STATUS_RANGE_LIST_CONFLICT
    00873
    00874 --*/
    00875 {
    00876     NTSTATUS status;
    00877     PRTLP_RANGE_LIST_ENTRY current, next, currentMerged, nextMerged;
    00878     BOOLEAN entryShared;
    00879
    00880     RTL_PAGED_CODE();
    00881     ASSERT(First);
    00882     ASSERT(Entry);
    00883
    00884     entryShared = SHARED(Entry);
    00885
    00886     //
    00887     // If we care about conflicts see if we conflict with anyone
    00888     //
    00889
    00890     if (!(AddRangeFlags & RTL_RANGE_LIST_ADD_IF_CONFLICT)) {
    00891
    00892         //
    00893         // Examine all ranges after the first intersecting one
    00894         //
    00895
    00896         current = First;
    00897         FOR_REST_IN_LIST(RTLP_RANGE_LIST_ENTRY, ListHead, current) {
    00898
    00899             if (Entry->End < current->Start) {
    00900
    00901                 //
    00902                 // We don't intersect anymore so there arn't any more
    00903                 // conflicts
    00904                 //
    00905
    00906                 break;
    00907
    00908             } else if (MERGED(current)) {
    00909
    00910                 //
    00911                 // Check if any of the merged ranges conflict
    00912                 //
    00913
    00914                 FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY,
    00915                                 &current->Merged.ListHead,
    00916                                 currentMerged) {
    00917
    00918                     //
    00919                     // Do we conflict?
    00920                     //
    00921
    00922                     if (RANGE_INTERSECT(currentMerged, Entry)
    00923                     && !(entryShared && SHARED(currentMerged))) {
    00924
    00925                         //
    00926                         // We conflict with one of the merged ranges
    00927                         //
    00928
    00929                         return STATUS_RANGE_LIST_CONFLICT;
    00930
    00931                     }
    00932                 }
    00933
    00934             } else if (!(entryShared && SHARED(current))) {
    00935
    00936                 //
    00937                 // We conflict with a non shared region in the  main list.
    00938                 //
    00939
    00940                 return STATUS_RANGE_LIST_CONFLICT;
    00941             }
    00942         }
    00943     }
    00944
    00945     //
    00946     // Ok - either we didn't find any conflicts or we don't care about
    00947     // them.  Now its safe to perform the merge.   Make the first
    00948     // overlapping range into a header if it is not already one and then
    00949     // add the rest of the ranges
    00950     //
    00951
    00952     if (!MERGED(First)) {
    00953
    00954         status = RtlpConvertToMergedRange(First);
    00955
    00956         if (!NT_SUCCESS(status)) {
    00957             goto cleanup;
    00958         }
    00959
    00960     }
    00961
    00962     ASSERT(MERGED(First));
    00963
    00964     current = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(First->ListEntry.Flink);
    00965
    00966     //
    00967     // Consider the entries between the one following first and the last
    00968     // intersecting one.
    00969     //
    00970
    00971     FOR_REST_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY, ListHead, current, next) {
    00972
    00973          if (Entry->End < current->Start) {
    00974
    00975             //
    00976             // We don't intersect any more
    00977             //
    00978
    00979             break;
    00980          }
    00981
    00982         if (MERGED(current)) {
    00983
    00984             //
    00985             // Add all the merged ranges to the new entry
    00986             //
    00987
    00988             FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    00989                                  &current->Merged.ListHead,
    00990                                  currentMerged,
    00991                                  nextMerged) {
    00992
    00993                 //
    00994                 // Remove the entry from the current list
    00995                 //
    00996
    00997                 RemoveEntryList(&currentMerged->ListEntry);
    00998
    00999                 //
    01000                 // Add the entry to the new merged range
    01001                 //
    01002
    01003                 status = RtlpAddToMergedRange(First,
    01004                                             currentMerged,
    01005                                             AddRangeFlags
    01006                                             );
    01007
    01008                 //
    01009                 // We should not be able to fail the add but just to be
    01010                 // on the safe side...
    01011                 //
    01012
    01013                 ASSERT(NT_SUCCESS(status));
    01014
    01015             }
    01016
    01017             //
    01018             // Remove and free the now empty header
    01019             //
    01020
    01021             ASSERT(IsListEmpty(&current->Merged.ListHead));
    01022
    01023             RemoveEntryList(&current->ListEntry);
    01024             RtlpFreeRangeListEntry(current);
    01025
    01026         } else {
    01027
    01028             //
    01029             // Remove the entry from the main list
    01030             //
    01031
    01032             RemoveEntryList(&current->ListEntry);
    01033
    01034             //
    01035             // Add the entry to the new merged range
    01036             //
    01037
    01038             status = RtlpAddToMergedRange(First,
    01039                                         current,
    01040                                         AddRangeFlags
    01041                                         );
    01042
    01043             //
    01044             // We should not be able to fail the add but just to be
    01045             // on the safe side...
    01046             //
    01047
    01048             ASSERT(NT_SUCCESS(status));
    01049
    01050         }
    01051     }
    01052
    01053     //
    01054     // Finally add the entry that did the overlapping
    01055     //
    01056
    01057     status = RtlpAddToMergedRange(First,
    01058                                 Entry,
    01059                                 AddRangeFlags
    01060                                 );
    01061
    01062     ASSERT(NT_SUCCESS(status));
    01063
    01064 cleanup:
    01065
    01066     return status;
    01067
    01068 }
    01069
    01070 NTSTATUS
    01071 RtlDeleteRange(
    01072     IN OUT PRTL_RANGE_LIST RangeList,
    01073     IN ULONGLONG Start,
    01074     IN ULONGLONG End,
    01075     IN PVOID Owner
    01076     )
    01077 /*++
    01078
    01079 Routine Description:
    01080
    01081     This routine deletes a range from a range list.
    01082
    01083 Arguments:
    01084
    01085     Start - The location of the start of the range to be deleted.
    01086
    01087     End - The location of the end of the range to be deleted.
    01088
    01089     Owner -  The owner of the range to be deleted, used to distinguish the
    01090     range from another with the same start and end.
    01091
    01092 Return Value:
    01093
    01094     Status code that indicates whether or not the function was successful:
    01095
    01096     STATUS_INSUFFICIENT_RESOURCES
    01097     STATUS_RANGE_LIST_CONFLICT
    01098
    01099 --*/
    01100 {
    01101     NTSTATUS status = STATUS_RANGE_NOT_FOUND;
    01102     PRTLP_RANGE_LIST_ENTRY current, next, currentMerged, nextMerged;
    01103
    01104     RTL_PAGED_CODE();
    01105     ASSERT(RangeList);
    01106
    01107     DEBUG_PRINT(1,
    01108         ("RtlDeleteRange(0x%08x, 0x%I64x, 0x%I64x, 0x%08x)\n",
    01109         RangeList,
    01110         Start,
    01111         End,
    01112         Owner
    01113         ));
    01114
    01115
    01116     FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01117                          &RangeList->ListHead,
    01118                          current,
    01119                          next) {
    01120
    01121         //
    01122         // We're passed all possible intersections
    01123         //
    01124
    01125         if (End < current->Start) {
    01126
    01127             //
    01128             // We didn't find a match
    01129             //
    01130
    01131             break;
    01132         }
    01133
    01134         if (MERGED(current)) {
    01135
    01136             //
    01137             // COuld our range exist in this merged range?
    01138             //
    01139
    01140             if (Start >= current->Start && End <= current->End) {
    01141
    01142                 FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01143                                      &current->Merged.ListHead,
    01144                                      currentMerged,
    01145                                      nextMerged) {
    01146
    01147                     if (currentMerged->Start == Start
    01148                     && currentMerged->End == End
    01149                     && currentMerged->Allocated.Owner == Owner) {
    01150
    01151                         //
    01152                         // This is the range - delete it and rebuild the merged
    01153                         // range appropriately
    01154                         //
    01155
    01156                         status = RtlpDeleteFromMergedRange(currentMerged,
    01157                                                          current
    01158                                                          );
    01159                         goto exit;
    01160                     }
    01161
    01162                 }
    01163             }
    01164
    01165         } else if (current->Start == Start
    01166                && current->End == End
    01167                && current->Allocated.Owner == Owner) {
    01168
    01169             //
    01170             // This is the range - delete it!
    01171             //
    01172
    01173             RemoveEntryList(&current->ListEntry);
    01174             RtlpFreeRangeListEntry(current);
    01175             status = STATUS_SUCCESS;
    01176             goto exit;
    01177         }
    01178     }
    01179
    01180 exit:
    01181
    01182     if (NT_SUCCESS(status)) {
    01183
    01184         //
    01185         // We have removed a range so decrement the count in the header
    01186         //
    01187
    01188         RangeList->Count--;
    01189         RangeList->Stamp++;
    01190
    01191     }
    01192
    01193     return status;
    01194 }
    01195
    01196 NTSTATUS
    01197 RtlDeleteOwnersRanges(
    01198     IN OUT PRTL_RANGE_LIST RangeList,
    01199     IN PVOID Owner
    01200     )
    01201 /*++
    01202
    01203 Routine Description:
    01204
    01205     This routine deletes all the ranges owned by a specific owner from a range
    01206     list.
    01207
    01208 Arguments:
    01209
    01210     Owner -  The owner of the ranges to be deleted.
    01211
    01212 Return Value:
    01213
    01214     Status code that indicates whether or not the function was successful:
    01215
    01216     STATUS_INSUFFICIENT_RESOURCES
    01217
    01218 --*/
    01219 {
    01220     NTSTATUS status = STATUS_SUCCESS;
    01221     PRTLP_RANGE_LIST_ENTRY current, next, currentMerged, nextMerged;
    01222
    01223     RTL_PAGED_CODE();
    01224     ASSERT(RangeList);
    01225
    01226     DEBUG_PRINT(1,
    01227                 ("RtlDeleteOwnersRanges(0x%08x, 0x%08x)\n",
    01228                 RangeList,
    01229                 Owner
    01230                 ));
    01231
    01232 findNext:
    01233
    01234     FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01235                          &RangeList->ListHead,
    01236                          current,
    01237                          next) {
    01238
    01239         if (MERGED(current)) {
    01240
    01241             FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01242                                  &current->Merged.ListHead,
    01243                                  currentMerged,
    01244                                  nextMerged) {
    01245
    01246                 if (currentMerged->Allocated.Owner == Owner) {
    01247
    01248                     //
    01249                     // This is the range - delete it and rebuild the merged
    01250                     // range appropriately
    01251                     //
    01252
    01253                     DEBUG_PRINT(2,
    01254                         ("RtlDeleteOwnersRanges: Deleting merged range \
    01255                             (Start=%I64x, End=%I64x)\n",
    01256                         currentMerged->Start,
    01257                         currentMerged->End
    01258                         ));
    01259
    01260                     status = RtlpDeleteFromMergedRange(currentMerged,
    01261                                                      current
    01262                                                      );
    01263                     if (!NT_SUCCESS(status)) {
    01264                         goto cleanup;
    01265                     }
    01266
    01267                     RangeList->Count--;
    01268                     RangeList->Stamp++;
    01269
    01270                     //
    01271                     // Can't keep scanning the list as it might have changed
    01272                     // underneath us - start from the beginning again...
    01273                     //
    01274                     // BUGBUG - could keep a last safe position to go from...
    01275                     //
    01276                     goto findNext;
    01277
    01278                 }
    01279             }
    01280
    01281         } else if (current->Allocated.Owner == Owner) {
    01282
    01283             //
    01284             // This is the range - delete it!
    01285             //
    01286
    01287             RemoveEntryList(&current->ListEntry);
    01288             RtlpFreeRangeListEntry(current);
    01289
    01290             DEBUG_PRINT(2,
    01291                 ("RtlDeleteOwnersRanges: Deleting range (Start=%I64x,End=%I64x)\n",
    01292                 current->Start,
    01293                 current->End
    01294                 ));
    01295
    01296             RangeList->Count--;
    01297             RangeList->Stamp++;
    01298
    01299             status = STATUS_SUCCESS;
    01300
    01301         }
    01302     }
    01303
    01304 cleanup:
    01305
    01306     return status;
    01307
    01308 }
    01309
    01310 NTSTATUS
    01311 RtlpDeleteFromMergedRange(
    01312     IN PRTLP_RANGE_LIST_ENTRY Delete,
    01313     IN PRTLP_RANGE_LIST_ENTRY Merged
    01314     )
    01315 /*++
    01316
    01317 Routine Description:
    01318
    01319     This routine deletes a range from a merged range and rebuilds the merged
    01320     range as appropriate.  This includes adding new merged and unmerged ranges.
    01321     If no ranges are left in the merged range it will be deleted.
    01322
    01323 Arguments:
    01324
    01325     BUGBUG these comments are not for this routine.
    01326
    01327     Start - The location of the start of the range to be deleted.
    01328
    01329     End - The location of the end of the range to be deleted.
    01330
    01331     Owner -  The owner of the range to be deleted, used to distinguish the
    01332     range from another with the same start and end.
    01333
    01334 Return Value:
    01335
    01336     Status code that indicates whether or not the function was successful:
    01337
    01338     STATUS_INSUFFICIENT_RESOURCES
    01339
    01340 --*/
    01341 {
    01342     NTSTATUS status = STATUS_SUCCESS;
    01343     PRTLP_RANGE_LIST_ENTRY current, next;
    01344     LIST_ENTRY keepList;
    01345     PLIST_ENTRY previousInsert, nextInsert;
    01346
    01347     RTL_PAGED_CODE();
    01348     ASSERT(MERGED(Merged));
    01349
    01350     //
    01351     // Remove the entry
    01352     //
    01353
    01354     RemoveEntryList(&Delete->ListEntry);
    01355
    01356     //
    01357     // Initialize the temporary list where the new list will be build
    01358     //
    01359
    01360     InitializeListHead(&keepList);
    01361
    01362     //
    01363     // Add the previously merged ranges into the keep list and put
    01364     // any duplicates of the delete range into the delete list
    01365     //
    01366
    01367     FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01368                          &Merged->Merged.ListHead,
    01369                          current,
    01370                          next) {
    01371
    01372         //
    01373         // Add it to the keepList.  Explicitly remove the entries from the
    01374         // list so it is still valid if we need to rebuild it.
    01375         //
    01376
    01377         RemoveEntryList(&current->ListEntry);
    01378
    01379         //
    01380         // Clear the conflict flag - if there is still a conflict RtlpAddRange
    01381         // should set it again.
    01382         //
    01383
    01384         current->PublicFlags &= ~RTL_RANGE_CONFLICT;
    01385
    01386         status = RtlpAddRange(&keepList,
    01387                               current,
    01388                               RTL_RANGE_LIST_ADD_IF_CONFLICT
    01389                              );
    01390
    01391         if (!NT_SUCCESS(status)) {
    01392             //
    01393             // This should only happen if we run out of pool
    01394             //
    01395             goto cleanup;
    01396         }
    01397     }
    01398
    01399     if (!IsListEmpty(&keepList)) {
    01400
    01401         //
    01402         // Everything went well so splice this temporary list into the
    01403         // main list where Merged used to be
    01404         //
    01405
    01406         previousInsert = Merged->ListEntry.Blink;
    01407         nextInsert = Merged->ListEntry.Flink;
    01408
    01409         previousInsert->Flink = keepList.Flink;
    01410         keepList.Flink->Blink = previousInsert;
    01411
    01412         nextInsert->Blink = keepList.Blink;
    01413         keepList.Blink->Flink = nextInsert;
    01414
    01415     } else {
    01416
    01417         RemoveEntryList(&Merged->ListEntry);
    01418
    01419     }
    01420
    01421     //
    01422     // Finally free the range we deleted and the merged range we have orphaned
    01423     //
    01424
    01425     RtlpFreeRangeListEntry(Delete);
    01426     RtlpFreeRangeListEntry(Merged);
    01427
    01428     return status;
    01429
    01430 cleanup:
    01431
    01432     //
    01433     // Things went wrong - should only be a STATUS_INSUFFICIENT_RESOURCES
    01434     // Reconstruct the list as it was before the call using the keepList and
    01435     // deleteList.
    01436     //
    01437
    01438     ASSERT(status == STATUS_INSUFFICIENT_RESOURCES);
    01439
    01440     //
    01441     // Add all the ranges we moved to the keepList back into Merged
    01442     //
    01443
    01444     FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY, &keepList, current, next) {
    01445
    01446         status = RtlpAddToMergedRange(Merged,
    01447                                     current,
    01448                                     RTL_RANGE_LIST_ADD_IF_CONFLICT
    01449                                     );
    01450
    01451         ASSERT(NT_SUCCESS(status));
    01452     }
    01453
    01454     //
    01455     // And the one were meant to delete
    01456     //
    01457
    01458     status = RtlpAddToMergedRange(Merged,
    01459                                   Delete,
    01460                                   RTL_RANGE_LIST_ADD_IF_CONFLICT
    01461                                  );
    01462
    01463     return status;
    01464 }
    01465
    01466 PRTLP_RANGE_LIST_ENTRY
    01467 RtlpCopyRangeListEntry(
    01468     PRTLP_RANGE_LIST_ENTRY Entry
    01469     )
    01470 /*++
    01471
    01472 Routine Description:
    01473
    01474     This routine copies a range list entry.  If the entry is merged all the
    01475     member ranges are copied too.
    01476
    01477 Arguments:
    01478
    01479     Entry - the range list entry to be copied.
    01480
    01481 Return Value:
    01482
    01483     Pointer to the new range list entry or NULL if a new entry could not be
    01484     allocated.
    01485
    01486 --*/
    01487 {
    01488     PRTLP_RANGE_LIST_ENTRY newEntry;
    01489
    01490     RTL_PAGED_CODE();
    01491     ASSERT(Entry);
    01492
    01493     if (newEntry = RtlpAllocateRangeListEntry()) {
    01494
    01495         RtlCopyMemory(newEntry, Entry, sizeof(RTLP_RANGE_LIST_ENTRY));
    01496
    01497 #if DBG
    01498         newEntry->ListEntry.Flink = NULL;
    01499         newEntry->ListEntry.Blink = NULL;
    01500 #endif
    01501
    01502         if (MERGED(Entry)) {
    01503
    01504             //
    01505             // Copy the merged list
    01506             //
    01507
    01508             PRTLP_RANGE_LIST_ENTRY current, newMerged;
    01509
    01510             InitializeListHead(&newEntry->Merged.ListHead);
    01511
    01512             FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY,
    01513                             &Entry->Merged.ListHead,
    01514                             current) {
    01515
    01516                 //
    01517                 // Allocate a new entry and copy the contents
    01518                 //
    01519
    01520                 newMerged = RtlpAllocateRangeListEntry();
    01521
    01522                 if (!newMerged) {
    01523                     goto cleanup;
    01524                 }
    01525
    01526                 RtlCopyMemory(newMerged, current, sizeof(RTLP_RANGE_LIST_ENTRY));
    01527
    01528                 //
    01529                 // Insert the new entry
    01530                 //
    01531
    01532                 InsertTailList(&newEntry->Merged.ListHead, &newMerged->ListEntry);
    01533             }
    01534         }
    01535     }
    01536
    01537     return newEntry;
    01538
    01539 cleanup:
    01540
    01541     //
    01542     // Free the partially build copy
    01543     //
    01544
    01545     RtlpDeleteRangeListEntry(newEntry);
    01546
    01547     return NULL;
    01548
    01549 }
    01550
    01551 NTSTATUS
    01552 RtlCopyRangeList(
    01553     OUT PRTL_RANGE_LIST CopyRangeList,
    01554     IN PRTL_RANGE_LIST RangeList
    01555     )
    01556 /*++
    01557
    01558 Routine Description:
    01559
    01560     This routine copies a range list.
    01561
    01562 Arguments:
    01563
    01564     CopyRangeList - An initialized but empty range list where RangeList should
    01565         be copied to.
    01566
    01567     RangeList - The range list that is to be copied.
    01568
    01569 Return Value:
    01570
    01571     Status code that indicates whether or not the function was successful:
    01572
    01573     STATUS_INSUFFICIENT_RESOURCES
    01574     STATUS_INVALID_PARAMETER
    01575
    01576 --*/
    01577 {
    01578
    01579     NTSTATUS status = STATUS_SUCCESS;
    01580     PRTLP_RANGE_LIST_ENTRY current, newEntry, currentMerged, newMerged;
    01581
    01582     RTL_PAGED_CODE();
    01583     ASSERT(RangeList);
    01584     ASSERT(CopyRangeList);
    01585
    01586
    01587     DEBUG_PRINT(1,
    01588                 ("RtlCopyRangeList(0x%08x, 0x%08x)\n",
    01589                 CopyRangeList,
    01590                 RangeList
    01591                 ));
    01592
    01593     //
    01594     // Sanity checks...
    01595     //
    01596
    01597     if (CopyRangeList->Count != 0) {
    01598         return STATUS_INVALID_PARAMETER;
    01599     }
    01600
    01601     //
    01602     // Copy the header information
    01603     //
    01604
    01605     CopyRangeList->Flags = RangeList->Flags;
    01606     CopyRangeList->Count = RangeList->Count;
    01607     CopyRangeList->Stamp = RangeList->Stamp;
    01608
    01609     //
    01610     // Perform the copy
    01611     //
    01612
    01613     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY, &RangeList->ListHead, current) {
    01614
    01615         //
    01616         // Copy the current entry
    01617         //
    01618
    01619         newEntry = RtlpCopyRangeListEntry(current);
    01620
    01621         if (!newEntry) {
    01622             status = STATUS_INSUFFICIENT_RESOURCES;
    01623             goto cleanup;
    01624         }
    01625
    01626         //
    01627         // Add it into the list
    01628         //
    01629
    01630         InsertTailList(&CopyRangeList->ListHead, &newEntry->ListEntry);
    01631     }
    01632
    01633     return status;
    01634
    01635 cleanup:
    01636
    01637     //
    01638     // Free up the partially complete range list
    01639     //
    01640
    01641     RtlFreeRangeList(CopyRangeList);
    01642     return status;
    01643
    01644 }
    01645
    01646 VOID
    01647 RtlpDeleteRangeListEntry(
    01648     IN PRTLP_RANGE_LIST_ENTRY Entry
    01649     )
    01650 /*++
    01651
    01652 Routine Description:
    01653
    01654     This routine deletes a range list entry - if the entry is merged then all
    01655     the member ranges will be deleted as well.  The entry will not be removed
    01656     from any list before deletion - this should be done before calling this
    01657     routine.
    01658
    01659 Arguments:
    01660
    01661     Entry - The entry to be deleted.
    01662
    01663 Return Value:
    01664
    01665     None
    01666
    01667 --*/
    01668
    01669 {
    01670     RTL_PAGED_CODE();
    01671
    01672     if (MERGED(Entry)) {
    01673
    01674         PRTLP_RANGE_LIST_ENTRY current, next;
    01675
    01676         //
    01677         // Free all member ranges first
    01678         //
    01679
    01680         FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01681                              &Entry->Merged.ListHead,
    01682                              current,
    01683                              next) {
    01684
    01685             RtlpFreeRangeListEntry(current);
    01686         }
    01687     }
    01688
    01689     RtlpFreeRangeListEntry(Entry);
    01690 }
    01691
    01692 VOID
    01693 RtlFreeRangeList(
    01694     IN PRTL_RANGE_LIST RangeList
    01695     )
    01696 /*++
    01697
    01698 Routine Description:
    01699
    01700     This routine deletes all the ranges in a range list.
    01701
    01702 Arguments:
    01703
    01704     RangeList - the range list to operate on.
    01705
    01706 Return Value:
    01707
    01708     None
    01709
    01710 --*/
    01711 {
    01712
    01713     PRTLP_RANGE_LIST_ENTRY current, next;
    01714
    01715     //
    01716     // Sanity checks...
    01717     //
    01718
    01719     RTL_PAGED_CODE();
    01720     ASSERT(RangeList);
    01721
    01722     //
    01723     // Clean up the header information
    01724     //
    01725
    01726     RangeList->Flags = 0;
    01727     RangeList->Count = 0;
    01728
    01729     FOR_ALL_IN_LIST_SAFE(RTLP_RANGE_LIST_ENTRY,
    01730                          &RangeList->ListHead,
    01731                          current,
    01732                          next) {
    01733
    01734         //
    01735         // Delete the current entry
    01736         //
    01737
    01738         RemoveEntryList(&current->ListEntry);
    01739         RtlpDeleteRangeListEntry(current);
    01740     }
    01741 }
    01742
    01743 NTSTATUS
    01744 RtlIsRangeAvailable(
    01745     IN PRTL_RANGE_LIST RangeList,
    01746     IN ULONGLONG Start,
    01747     IN ULONGLONG End,
    01748     IN ULONG Flags,
    01749     IN UCHAR AttributeAvailableMask,
    01750     IN PVOID Context OPTIONAL,
    01751     IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL,
    01752     OUT PBOOLEAN Available
    01753     )
    01754 /*++
    01755
    01756 Routine Description:
    01757
    01758     This routine determines if a given range is available.
    01759
    01760 Arguments:
    01761
    01762     RangeList - The range list to test availability on.
    01763
    01764     Start - The start of the range to test for availability.
    01765
    01766     End - The end of the range to test for availability.
    01767
    01768     Flags - Modify the behaviour of the routine.
    01769
    01770         RTL_RANGE_LIST_SHARED_OK - indicates that shared ranges should be
    01771             considered to be available.
    01772
    01773     AttributeAvailableMask - Any range encountered with any of these bits set will be
    01774         consideredto be available.
    01775
    01776     Available -  Pointer to a boolean which will be set to TRUE if the range
    01777         is available, otherwise FALSE;
    01778
    01779 Return Value:
    01780
    01781     Status code that indicates whether or not the function was successful:
    01782
    01783 --*/
    01784 {
    01785     NTSTATUS status;
    01786     RTL_RANGE_LIST_ITERATOR iterator;
    01787     PRTL_RANGE dummy;
    01788
    01789     RTL_PAGED_CODE();
    01790
    01791     ASSERT(RangeList);
    01792     ASSERT(Available);
    01793
    01794     DEBUG_PRINT(1,
    01795         ("RtlIsRangeAvailable(0x%08x, 0x%I64x, 0x%I64x, 0x%08x, 0x%08x)\n",
    01796         RangeList,
    01797         Start,
    01798         End,
    01799         Flags,
    01800         Available
    01801         ));
    01802
    01803     //
    01804     // Initialize iterator to the start of the list
    01805     //
    01806     status = RtlGetFirstRange(RangeList, &iterator, &dummy);
    01807
    01808
    01809     if (status == STATUS_NO_MORE_ENTRIES) {
    01810         //
    01811         // The range list is empty therefore the range is available
    01812         //
    01813
    01814         *Available = TRUE;
    01815         return STATUS_SUCCESS;
    01816
    01817     } else if (!NT_SUCCESS(status)) {
    01818
    01819         return status;
    01820
    01821     }
    01822
    01823     *Available = RtlpIsRangeAvailable(&iterator,
    01824                                       Start,
    01825                                       End,
    01826                                       AttributeAvailableMask,
    01827                                       (BOOLEAN)(Flags & RTL_RANGE_LIST_SHARED_OK),
    01828                                       (BOOLEAN)(Flags & RTL_RANGE_LIST_NULL_CONFLICT_OK),
    01829                                       TRUE,
    01830                                       Context,
    01831                                       Callback
    01832                                       );
    01833
    01834     return STATUS_SUCCESS;
    01835
    01836 }
    01837
    01838 BOOLEAN
    01839 RtlpIsRangeAvailable(
    01840     IN PRTL_RANGE_LIST_ITERATOR Iterator,
    01841     IN ULONGLONG Start,
    01842     IN ULONGLONG End,
    01843     IN UCHAR AttributeAvailableMask,
    01844     IN BOOLEAN SharedOK,
    01845     IN BOOLEAN NullConflictOK,
    01846     IN BOOLEAN Forward,
    01847     IN PVOID Context OPTIONAL,
    01848     IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL
    01849     )
    01850 /*++
    01851
    01852 Routine Description:
    01853
    01854     This routine determines if a given range is available.
    01855
    01856 Arguments:
    01857
    01858     Iterator - An iterator set to the first range to test in the range list.
    01859
    01860     Start - The start of the range to test for availability.
    01861
    01862     End - The end of the range to test for availability.
    01863
    01864     AttributeAvailableMask - Any range encountered with any of these bits set will be
    01865         considered to be available.
    01866
    01867     SharedOK - Indicated whether or not shared ranges are considered to be
    01868         available.
    01869
    01870 Return Value:
    01871
    01872     TRUE if the range is available, FALSE otherwise.
    01873
    01874 --*/
    01875 {
    01876     PRTL_RANGE current;
    01877
    01878     RTL_PAGED_CODE();
    01879
    01880     ASSERT(Iterator);
    01881
    01882     FOR_REST_OF_RANGES(Iterator, current, Forward) {
    01883
    01884         //
    01885         // If we have passed all possible intersections then break out.  This
    01886         // can't be done in a merged region because of possible overlaps.
    01887         //
    01888
    01889         if (Forward) {
    01890             if (!Iterator->MergedHead && End < current->Start) {
    01891                 break;
    01892             }
    01893         } else {
    01894             if (!Iterator->MergedHead && Start > current->End) {
    01895                 break;
    01896             }
    01897         }
    01898
    01899         //
    01900         // Do we intersect?
    01901         //
    01902         if (RANGE_LIMITS_INTERSECT(Start, End, current->Start, current->End)) {
    01903
    01904             DEBUG_PRINT(2,
    01905                 ("Intersection 0x%I64x-0x%I64x and 0x%I64x-0x%I64x\n",
    01906                 Start,
    01907                 End,
    01908                 current->Start,
    01909                 current->End
    01910                 ));
    01911
    01912             //
    01913             // Is the intersection not Ok because it is with a non-shared
    01914             // region or we don't want a shared region? Or the user said that
    01915             // it should be considered available because of the user flags set.
    01916             //
    01917
    01918             if (!((SharedOK && (current->Flags & RTL_RANGE_SHARED))
    01919                   || (current->Attributes & AttributeAvailableMask)
    01920                   || (NullConflictOK && (current->Owner == NULL))
    01921                   )
    01922                 )  {
    01923
    01924                 //
    01925                 // If the caller provided a callback to support extra conflict
    01926                 // semantics call it
    01927                 //
    01928
    01929                 if (ARGUMENT_PRESENT(Callback)) {
    01930                     if ((*Callback)(Context, (PRTL_RANGE)current)) {
    01931
    01932                     DEBUG_PRINT(2,
    01933                         ("User provided callback overrode conflict\n",
    01934                         Start,
    01935                         End,
    01936                         current->Start,
    01937                         current->End
    01938                         ));
    01939
    01940                         continue;
    01941                     }
    01942                 }
    01943
    01944                 return FALSE;
    01945             }
    01946         }
    01947     }
    01948
    01949
    01950     return TRUE;
    01951 }
    01952
    01953 NTSTATUS
    01954 RtlFindRange(
    01955     IN PRTL_RANGE_LIST RangeList,
    01956     IN ULONGLONG Minimum,
    01957     IN ULONGLONG Maximum,
    01958     IN ULONG Length,
    01959     IN ULONG Alignment,
    01960     IN ULONG Flags,
    01961     IN UCHAR AttributeAvailableMask,
    01962     IN PVOID Context OPTIONAL,
    01963     IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL,
    01964     OUT PULONGLONG Start
    01965     )
    01966 /*++
    01967
    01968 Routine Description:
    01969
    01970     This routine finds the first available range that meets the criterion specified.
    01971
    01972 Arguments:
    01973
    01974     RangeList - The range list to find a range in.
    01975
    01976     Minimum - The minimum acceptable value of the start of the range.
    01977
    01978     Maximum - The maximum acceptable value of the end of the range.
    01979
    01980     Length - The length of the range required.
    01981
    01982     Alignmnent - The alignment of the start of the range.
    01983
    01984     Flags - Modify the behaviour of the routine.
    01985
    01986         RTL_RANGE_LIST_SHARED_OK - indicates that shared ranges should be
    01987             considered to be available.
    01988
    01989     AttributeAvailableMask - Any range encountered with any of these bits set will be
    01990         considered to be available.
    01991
    01992     Start - Pointer to a ULONGLONG where the start value will be returned on
    01993         success.
    01994
    01995 Return Value:
    01996
    01997     Status code that indicates whether or not the function was successful:
    01998
    01999     STATUS_UNSUCCESSFUL
    02000     STATUS_INVALID_PARAMETER
    02001
    02002 --*/
    02003 {
    02004
    02005     ULONGLONG start, end;
    02006     RTL_RANGE_LIST_ITERATOR iterator;
    02007     PRTL_RANGE dummy;
    02008     BOOLEAN sharedOK, nullConflictOK;
    02009
    02010     RTL_PAGED_CODE();
    02011
    02012     ASSERT(RangeList);
    02013     ASSERT(Start);
    02014     ASSERT(Alignment > 0);
    02015     ASSERT(Length > 0);
    02016
    02017     DEBUG_PRINT(1,
    02018         ("RtlFindRange(0x%08x, 0x%I64x, 0x%I64x, 0x%08x, 0x%08x, 0x%08x, 0x%08x)\n",
    02019         RangeList,
    02020         Minimum,
    02021         Maximum,
    02022         Length,
    02023         Alignment,
    02024         Flags,
    02025         Start
    02026         ));
    02027
    02028     //
    02029     // Search from high to low, Align start if necessary
    02030     //
    02031
    02032     start = Maximum - (Length - 1);
    02033     start -= start % Alignment;
    02034
    02035     //
    02036     // Valiate parameters
    02037     //
    02038
    02039     if ((Minimum > Maximum)
    02040     || (Maximum - Minimum < Length - 1)
    02041     || (Minimum + Alignment < Minimum)
    02042     || (start < Minimum)
    02043     || (Length == 0)
    02044     || (Alignment == 0)) {
    02045
    02046         return STATUS_INVALID_PARAMETER;
    02047     }
    02048
    02049     sharedOK = (BOOLEAN) Flags & RTL_RANGE_LIST_SHARED_OK;
    02050     nullConflictOK = (BOOLEAN) Flags & RTL_RANGE_LIST_NULL_CONFLICT_OK;
    02051     //
    02052     // Calculate the end
    02053     //
    02054
    02055     end = start + Length - 1;
    02056
    02057     //
    02058     // Initialze the iterator to the end of the list
    02059     //
    02060
    02061     RtlGetLastRange(RangeList, &iterator, &dummy);
    02062
    02063     //
    02064     // Keep trying to find ranges until we run out of room or we
    02065     // wrap around
    02066     //
    02067
    02068     do {
    02069
    02070         DEBUG_PRINT(2,
    02071             ("RtlFindRange: Testing range %I64x-%I64x\n",
    02072             start,
    02073             end
    02074             ));
    02075
    02076         if (RtlpIsRangeAvailable(&iterator,
    02077                                  start,
    02078                                  end,
    02079                                  AttributeAvailableMask,
    02080                                  sharedOK,
    02081                                  nullConflictOK,
    02082                                  FALSE,
    02083                                  Context,
    02084                                  Callback)) {
    02085
    02086             *Start = start;
    02087
    02088             //
    02089             // Assert our result, if we produced one, is in the in
    02090             // the range specified
    02091             //
    02092
    02093             ASSERT(*Start >= Minimum && *Start + Length - 1 <= Maximum);
    02094
    02095             return STATUS_SUCCESS;
    02096         }
    02097
    02098         //
    02099         // Find a suitable range starting from the one we conflicted with,
    02100         // that is the current range in the iterator - this breaks the
    02101         // abstraction of the iterator in the name of efficiency.
    02102         //
    02103
    02104         start = ((PRTLP_RANGE_LIST_ENTRY)(iterator.Current))->Start;
    02105         if ((start - Length) > start) {
    02106
    02107             //
    02108             // Wrapped, fail.
    02109             //
    02110
    02111             break;
    02112         }
    02113
    02114         start -= Length;
    02115         start -= start % Alignment;
    02116         end = start + Length - 1;
    02117
    02118     } while ( start >= Minimum );
    02119
    02120     return STATUS_UNSUCCESSFUL;
    02121 }
    02122
    02123 NTSTATUS
    02124 RtlGetFirstRange(
    02125     IN PRTL_RANGE_LIST RangeList,
    02126     OUT PRTL_RANGE_LIST_ITERATOR Iterator,
    02127     OUT PRTL_RANGE *Range
    02128     )
    02129 /*++
    02130
    02131 Routine Description:
    02132
    02133     This routine extracts the first range in a range list.  If there are no
    02134     ranges then STATUS_NO_MORE_ENTRIES is returned.
    02135
    02136 Arguments:
    02137
    02138     RangeList - The range list to operate on.
    02139
    02140     Iterator - On success this contains the state of the iteration and can be
    02141         passed to RtlGetNextRange.
    02142
    02143     Range - On success this contains a pointer to the first range
    02144
    02145 Return Value:
    02146
    02147     Status code that indicates whether or not the function was successful:
    02148
    02149     STATUS_NO_MORE_ENTRIES
    02150
    02151 --*/
    02152 {
    02153     NTSTATUS status = STATUS_SUCCESS;
    02154     PRTLP_RANGE_LIST_ENTRY first;
    02155
    02156     RTL_PAGED_CODE();
    02157
    02158     //
    02159     // Fill in the first part of the iterator
    02160     //
    02161
    02162     Iterator->RangeListHead = &RangeList->ListHead;
    02163     Iterator->Stamp = RangeList->Stamp;
    02164
    02165     if (!IsListEmpty(&RangeList->ListHead)) {
    02166
    02167         first = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(RangeList->ListHead.Flink);
    02168
    02169         //
    02170         // Fill in the iterator and update to point to the first merged
    02171         // range if we are merged
    02172         //
    02173
    02174         if (MERGED(first)) {
    02175
    02176             ASSERT(!IsListEmpty(&first->Merged.ListHead));
    02177
    02178             Iterator->MergedHead = &first->Merged.ListHead;
    02179             Iterator->Current = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02180                                     first->Merged.ListHead.Flink
    02181                                     );
    02182
    02183         } else {
    02184
    02185             Iterator->MergedHead = NULL;
    02186             Iterator->Current = first;
    02187         }
    02188
    02189         *Range = (PRTL_RANGE) Iterator->Current;
    02190
    02191     } else {
    02192
    02193         Iterator->Current = NULL;
    02194         Iterator->MergedHead = NULL;
    02195
    02196         *Range = NULL;
    02197
    02198         status = STATUS_NO_MORE_ENTRIES;
    02199     }
    02200
    02201     return status;
    02202 }
    02203
    02204 NTSTATUS
    02205 RtlGetLastRange(
    02206     IN PRTL_RANGE_LIST RangeList,
    02207     OUT PRTL_RANGE_LIST_ITERATOR Iterator,
    02208     OUT PRTL_RANGE *Range
    02209     )
    02210 /*++
    02211
    02212 Routine Description:
    02213
    02214     This routine extracts the first range in a range list.  If there are no
    02215     ranges then STATUS_NO_MORE_ENTRIES is returned.
    02216
    02217 Arguments:
    02218
    02219     RangeList - The range list to operate on.
    02220
    02221     Iterator - On success this contains the state of the iteration and can be
    02222         passed to RtlGetNextRange.
    02223
    02224     Range - On success this contains a pointer to the first range
    02225
    02226 Return Value:
    02227
    02228     Status code that indicates whether or not the function was successful:
    02229
    02230     STATUS_NO_MORE_ENTRIES
    02231
    02232 --*/
    02233 {
    02234     NTSTATUS status = STATUS_SUCCESS;
    02235     PRTLP_RANGE_LIST_ENTRY first;
    02236
    02237     RTL_PAGED_CODE();
    02238
    02239     //
    02240     // Fill in the first part of the iterator
    02241     //
    02242
    02243     Iterator->RangeListHead = &RangeList->ListHead;
    02244     Iterator->Stamp = RangeList->Stamp;
    02245
    02246     if (!IsListEmpty(&RangeList->ListHead)) {
    02247
    02248         first = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(RangeList->ListHead.Blink);
    02249
    02250         //
    02251         // Fill in the iterator and update to point to the first merged
    02252         // range if we are merged
    02253         //
    02254
    02255         if (MERGED(first)) {
    02256
    02257             ASSERT(!IsListEmpty(&first->Merged.ListHead));
    02258
    02259             Iterator->MergedHead = &first->Merged.ListHead;
    02260             Iterator->Current = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02261                                     first->Merged.ListHead.Blink
    02262                                     );
    02263
    02264         } else {
    02265
    02266             Iterator->MergedHead = NULL;
    02267             Iterator->Current = first;
    02268         }
    02269
    02270         *Range = (PRTL_RANGE) Iterator->Current;
    02271
    02272     } else {
    02273
    02274         Iterator->Current = NULL;
    02275         Iterator->MergedHead = NULL;
    02276
    02277         *Range = NULL;
    02278
    02279         status = STATUS_NO_MORE_ENTRIES;
    02280     }
    02281
    02282     return status;
    02283 }
    02284
    02285 NTSTATUS
    02286 RtlGetNextRange(
    02287     IN OUT PRTL_RANGE_LIST_ITERATOR Iterator,
    02288     OUT    PRTL_RANGE *Range,
    02289     IN     BOOLEAN MoveForwards
    02290     )
    02291 /*++
    02292
    02293 Routine Description:
    02294
    02295     This routine extracts the next range in a range list.  If there are no
    02296     more ranges then STATUS_NO_MORE_ENTRIES is returned.
    02297
    02298 Arguments:
    02299
    02300     Iterator     - The iterator filled in by RtlGet{First|Next}Range which will
    02301                    be update on success.
    02302     Range        - On success this contains a pointer to the next range
    02303     MoveForwards - If true, go forwards thru the list, otherwise,
    02304                    go backwards.
    02305
    02306 Return Value:
    02307
    02308     Status code that indicates whether or not the function was successful:
    02309
    02310     STATUS_NO_MORE_ENTRIES
    02311     STATUS_INVALID_PARAMETER
    02312
    02313 Note:
    02314
    02315     Add/Delete operations can not be performed on the list between calls to
    02316     RtlGetFirstRange / RtlGetNextRange and RtlGetNextRange / RtlGetNextRange.
    02317     If such calls are made the routine will detect and fail the call.
    02318
    02319 --*/
    02320 {
    02321     PRTLP_RANGE_LIST_ENTRY mergedEntry, next;
    02322     PLIST_ENTRY entry;
    02323
    02324     RTL_PAGED_CODE();
    02325
    02326     //
    02327     // Make sure that we haven't changed the list between calls
    02328     //
    02329
    02330     if (RANGE_LIST_FROM_LIST_HEAD(Iterator->RangeListHead)->Stamp !=
    02331             Iterator->Stamp) {
    02332
    02333         ASSERTMSG(
    02334             "RtlGetNextRange: Add/Delete operations have been performed while \
    02335             iterating through a list\n", FALSE);
    02336
    02337         return STATUS_INVALID_PARAMETER;
    02338     }
    02339
    02340     //
    02341     // If we have already reached the end of the list then return
    02342     //
    02343
    02344     if (!Iterator->Current) {
    02345         *Range = NULL;
    02346         return STATUS_NO_MORE_ENTRIES;
    02347     }
    02348
    02349     entry = &((PRTLP_RANGE_LIST_ENTRY)(Iterator->Current))->ListEntry;
    02350     next = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02351                MoveForwards ? entry->Flink : entry->Blink);
    02352
    02353     ASSERT(next);
    02354
    02355     //
    02356     // Are we in a merged range?
    02357     //
    02358     if (Iterator->MergedHead) {
    02359
    02360         //
    02361         // Have we reached the end of the merged range?
    02362         //
    02363         if (&next->ListEntry == Iterator->MergedHead) {
    02364
    02365             //
    02366             // Get back to the merged entry
    02367             //
    02368             mergedEntry = CONTAINING_RECORD(
    02369                               Iterator->MergedHead,
    02370                               RTLP_RANGE_LIST_ENTRY,
    02371                               Merged.ListHead
    02372                               );
    02373
    02374             //
    02375             // Move on to the next entry in the main list
    02376             //
    02377
    02378             next = MoveForwards ?
    02379                        RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02380                            mergedEntry->ListEntry.Flink
    02381                            )
    02382                    :   RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02383                            mergedEntry->ListEntry.Blink
    02384                            );
    02385             Iterator->MergedHead = NULL;
    02386
    02387         } else {
    02388
    02389             //
    02390             // There are merged ranges left - return the next one
    02391             //
    02392             Iterator->Current = next;
    02393             *Range = (PRTL_RANGE) next;
    02394
    02395             return STATUS_SUCCESS;
    02396         }
    02397     }
    02398
    02399     //
    02400     // Have we reached the end of the main list?
    02401     //
    02402     if (&next->ListEntry == Iterator->RangeListHead) {
    02403
    02404         //
    02405         // Tell the caller there are no more ranges
    02406         //
    02407         Iterator->Current = NULL;
    02408         *Range = NULL;
    02409         return STATUS_NO_MORE_ENTRIES;
    02410
    02411     } else {
    02412
    02413         //
    02414         // Is the next range merged?
    02415         //
    02416
    02417         if (MERGED(next)) {
    02418
    02419             //
    02420             // Goto the first merged entry
    02421             //
    02422             ASSERT(!Iterator->MergedHead);
    02423
    02424             Iterator->MergedHead = &next->Merged.ListHead;
    02425             Iterator->Current = MoveForwards ?
    02426                                     RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02427                                         next->Merged.ListHead.Flink
    02428                                         )
    02429                                 :   RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02430                                         next->Merged.ListHead.Blink
    02431                                         );
    02432         } else {
    02433
    02434             //
    02435             // Go to the next entry in the main list
    02436             //
    02437
    02438             Iterator->Current = RANGE_LIST_ENTRY_FROM_LIST_ENTRY(
    02439                                     &next->ListEntry
    02440                                     );
    02441         }
    02442
    02443         *Range = (PRTL_RANGE) Iterator->Current;
    02444     }
    02445
    02446     return STATUS_SUCCESS;
    02447 }
    02448
    02449 NTSTATUS
    02450 RtlMergeRangeLists(
    02451     OUT PRTL_RANGE_LIST MergedRangeList,
    02452     IN PRTL_RANGE_LIST RangeList1,
    02453     IN PRTL_RANGE_LIST RangeList2,
    02454     IN ULONG Flags
    02455     )
    02456 /*++
    02457
    02458 Routine Description:
    02459
    02460     This routine merges two range lists into one.
    02461
    02462 Arguments:
    02463
    02464     MergedRangeList - An empty range list where on success the result of the
    02465         merge will be placed.
    02466
    02467     RangeList1 - One of the range lists to be merged.
    02468
    02469     RangeList2 - The other the range list to merged.
    02470
    02471     Flags - Modifies the behaviour of the routine:
    02472
    02473         RTL_RANGE_LIST_MERGE_IF_CONFLICT - Merged ranges even if the conflict.
    02474
    02475 Return Value:
    02476
    02477     Status code that indicates whether or not the function was successful:
    02478
    02479     STATUS_INSUFFICIENT_RESOURCES
    02480     STATUS_RANGE_LIST_CONFLICT
    02481
    02482 --*/
    02483 {
    02484     NTSTATUS status;
    02485     PRTLP_RANGE_LIST_ENTRY current, currentMerged, newEntry;
    02486     ULONG addFlags;
    02487
    02488     RTL_PAGED_CODE();
    02489
    02490     DEBUG_PRINT(1,
    02491             ("RtlMergeRangeList(0x%08x, 0x%08x, 0x%08x, 0x%08x)\n",
    02492             MergedRangeList,
    02493             RangeList1,
    02494             RangeList2,
    02495             Flags
    02496             ));
    02497
    02498     //
    02499     // Copy the first range list
    02500     //
    02501
    02502     status = RtlCopyRangeList(MergedRangeList, RangeList1);
    02503
    02504     if (!NT_SUCCESS(status)) {
    02505         goto cleanup;
    02506     }
    02507
    02508     //
    02509     // Add all ranges from 2nd list
    02510     //
    02511
    02512     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY, &RangeList2->ListHead, current) {
    02513
    02514         if (MERGED(current)) {
    02515
    02516             FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY,
    02517                             &current->Merged.ListHead,
    02518                             currentMerged) {
    02519
    02520                 if (!(newEntry = RtlpCopyRangeListEntry(currentMerged))) {
    02521                         status = STATUS_INSUFFICIENT_RESOURCES;
    02522                         goto cleanup;
    02523                 }
    02524
    02525                 if (CONFLICT(currentMerged)) {
    02526
    02527                     //
    02528                     // If a range was already conflicting in then it will conflict in
    02529                     // the merged range list - allow this.
    02530                     //
    02531
    02532                     addFlags = Flags | RTL_RANGE_LIST_ADD_IF_CONFLICT;
    02533                 } else {
    02534
    02535                     addFlags = Flags;
    02536                 }
    02537
    02538                 status = RtlpAddRange(&MergedRangeList->ListHead,
    02539                                       newEntry,
    02540                                       addFlags
    02541                                       );
    02542
    02543             }
    02544
    02545         } else {
    02546
    02547
    02548             if (!(newEntry = RtlpCopyRangeListEntry(current))){
    02549                 status = STATUS_INSUFFICIENT_RESOURCES;
    02550                 goto cleanup;
    02551             }
    02552
    02553             if (CONFLICT(current)) {
    02554
    02555                 //
    02556                 // If a range was already conflicting in then it will conflict in
    02557                 // the merged range list - allow this.
    02558                 //
    02559
    02560                 addFlags = Flags | RTL_RANGE_LIST_ADD_IF_CONFLICT;
    02561             } else {
    02562                 addFlags = Flags;
    02563             }
    02564
    02565             status = RtlpAddRange(&MergedRangeList->ListHead,
    02566                                   newEntry,
    02567                                   addFlags
    02568                                   );
    02569
    02570             if (!NT_SUCCESS(status)) {
    02571                 goto cleanup;
    02572             }
    02573         }
    02574
    02575     }
    02576     //
    02577     // Correct the count
    02578     //
    02579
    02580     MergedRangeList->Count += RangeList2->Count;
    02581     MergedRangeList->Stamp += RangeList2->Count;
    02582
    02583     return status;
    02584
    02585 cleanup:
    02586
    02587     //
    02588     // Something went wrong... Free up what we have built of the
    02589     // new list and return the error
    02590     //
    02591
    02592     RtlFreeRangeList(MergedRangeList);
    02593
    02594     return status;
    02595
    02596 }
    02597
    02598 NTSTATUS
    02599 RtlInvertRangeList(
    02600     OUT PRTL_RANGE_LIST InvertedRangeList,
    02601     IN PRTL_RANGE_LIST RangeList
    02602     )
    02603 /*
    02604
    02605 Routine Description:
    02606
    02607     This inverts a range list so that all areas which are allocated
    02608     in InvertedRangeList will not be in RangeList, and vice
    02609     versa. The ranges in InvertedRangeList will all be owned by NULL.
    02610
    02611 Arguments:
    02612
    02613     InvertedRangeList - a pointer to an empty Range List to be filled
    02614         with the inverted list
    02615
    02616     RangeList - a pointer to the Range List to be inverted
    02617
    02618 Return Value:
    02619
    02620     Status of operation.
    02621
    02622 */
    02623
    02624 {
    02625
    02626     PRTLP_RANGE_LIST_ENTRY currentRange;
    02627     ULONGLONG currentStart = 0;
    02628     NTSTATUS status;
    02629
    02630     RTL_PAGED_CODE();
    02631
    02632     //
    02633     // if Inverted List does not start out empty, the inverted list
    02634     // is meaningless
    02635     //
    02636
    02637     ASSERT(InvertedRangeList->Count == 0);
    02638
    02639     //
    02640     // iterate through all elements of the ReverseAllocation
    02641     // adding the unallocated part before the current element
    02642     // to the RealAllocation
    02643     //
    02644
    02645     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY,
    02646                     &RangeList->ListHead,
    02647                     currentRange) {
    02648
    02649         if (currentRange->Start > currentStart) {
    02650
    02651             //
    02652             // we want a NULL range owner to show that the
    02653             // range is unavailable
    02654             //
    02655             status = RtlAddRange(InvertedRangeList,
    02656                                  currentStart,
    02657                                  currentRange->Start-1,
    02658                                  0,            // Attributes
    02659                                  0,            // Flags
    02660                                  0,            // UserData
    02661                                  NULL);        // Owner
    02662
    02663             if (!NT_SUCCESS(status)) {
    02664                 return status;
    02665             }
    02666         }
    02667
    02668         currentStart = currentRange->End + 1;
    02669     }
    02670
    02671     //
    02672     // add the portion of the address space above the last
    02673     // element in the ReverseAllocation to the RealAllocation
    02674     //
    02675     // unless we've wrapped, in which case we've already added
    02676     // the last element
    02677     //
    02678
    02679     if (currentStart > (currentStart - 1)) {
    02680
    02681         status = RtlAddRange(InvertedRangeList,
    02682                              currentStart,
    02683                              MAX_ULONGLONG,
    02684                              0,
    02685                              0,
    02686                              0,
    02687                              NULL);
    02688
    02689         if (!NT_SUCCESS(status)) {
    02690             return status;
    02691         }
    02692     }
    02693
    02694     return STATUS_SUCCESS;
    02695
    02696 }
    02697
    02698
    02699 #if DBG
    02700
    02701 VOID
    02702 RtlpDumpRangeListEntry(
    02703     LONG Level,
    02704     PRTLP_RANGE_LIST_ENTRY Entry,
    02705     BOOLEAN Indent
    02706     )
    02707 {
    02708     PWSTR indentString;
    02709     PRTLP_RANGE_LIST_ENTRY current;
    02710
    02711     RTL_PAGED_CODE();
    02712
    02713     if (Indent) {
    02714         indentString = L"\t\t";
    02715     } else {
    02716         indentString = L"";
    02717     }
    02718     //
    02719     // Print the range
    02720     //
    02721
    02722     DEBUG_PRINT(Level,
    02723                 ("%sRange (0x%08x): 0x%I64x-0x%I64x\n",
    02724                 indentString,
    02725                 Entry,
    02726                 Entry->Start,
    02727                 Entry->End
    02728                 ));
    02729
    02730     //
    02731     // Print the flags
    02732     //
    02733
    02734     DEBUG_PRINT(Level, ("%s\tPrivateFlags: ", indentString));
    02735
    02736     if (MERGED(Entry)) {
    02737         DEBUG_PRINT(Level, ("MERGED "));
    02738
    02739     }
    02740
    02741     DEBUG_PRINT(Level, ("\n%s\tPublicFlags: ", indentString));
    02742
    02743     if (SHARED(Entry)) {
    02744         DEBUG_PRINT(Level, ("SHARED "));
    02745     }
    02746
    02747     if (CONFLICT(Entry)) {
    02748         DEBUG_PRINT(Level, ("CONFLICT "));
    02749     }
    02750
    02751     DEBUG_PRINT(Level, ("\n"));
    02752
    02753
    02754     if (MERGED(Entry)) {
    02755
    02756         DEBUG_PRINT(Level, ("%sMerged entries:\n", indentString));
    02757
    02758         //
    02759         // Print the merged entries
    02760         //
    02761
    02762         FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY,
    02763                         &Entry->Merged.ListHead,
    02764                         current) {
    02765             RtlpDumpRangeListEntry(Level, current, TRUE);
    02766         }
    02767
    02768
    02769     } else {
    02770
    02771         //
    02772         // Print the other data
    02773         //
    02774
    02775         DEBUG_PRINT(Level,
    02776             ("%s\tUserData: 0x%08x\n\tOwner: 0x%08x\n",
    02777             indentString,
    02778             Entry->Allocated.UserData,
    02779             Entry->Allocated.Owner
    02780             ));
    02781     }
    02782 }
    02783
    02784 VOID
    02785 RtlpDumpRangeList(
    02786     LONG Level,
    02787     PRTL_RANGE_LIST RangeList
    02788     )
    02789
    02790 {
    02791     PRTLP_RANGE_LIST_ENTRY current, currentMerged;
    02792
    02793     RTL_PAGED_CODE();
    02794
    02795     DEBUG_PRINT(Level,
    02796                 ("*** Range List (0x%08x) - Count: %i\n",
    02797                 RangeList,
    02798                 RangeList->Count
    02799                 ));
    02800
    02801     FOR_ALL_IN_LIST(RTLP_RANGE_LIST_ENTRY, &RangeList->ListHead, current) {
    02802
    02803         //
    02804         // Print the entry
    02805         //
    02806
    02807         RtlpDumpRangeListEntry(Level, current, FALSE);
    02808     }
    02809 }
    02810
    02811 #endif