ulib/region-alloc/region-alloc.cpp

31     // We should have the same number of regions sorted by base address and by
87     // base address as well as size)
92     to_add->base = region.base;
113     // Find the region whose base address is <= the specified region (if any).
120     auto before = avail_regions_by_base_.upper_bound(region.base);
122     uint64_t region_end = region.base + region.size;  // exclusive end
126         before_end = before->base + before->size;  // exclusive end
127         if ((region.base >= before->base) && (region_end <= before_end)) {
132             if ((region.base == before->base) && (region_end == before_end)) {
145             if ((region.base != before->base) && (region_end != before_end)) {
150                 // Looks like we have the memory we need.  Compute the base/size of
155                 first->size  = region.base - first->base;
156                 second->base = region_end;
165             // Case 3: region trims the front of before.  Update before's base and
167             // no need to recompute its position in the base index, this has not
169             if (region.base == before->base) {
173                 bptr->base += region.size;
182             ZX_DEBUG_ASSERT(region.base != before->base);
207         ZX_DEBUG_ASSERT(region.base >= before->base);
209         if (before_end > region.base) {
213             // If before's base is the same as the region's base, then we are
216             if (bptr->base == region.base) {
222                 bptr->size = region.base - bptr->base;
228             region.base = before_end;
229             region.size = region_end - region.base;
234     // While there are regions whose base address comes after the base address
243         ZX_DEBUG_ASSERT(after->base > region.base);
246         if (after->base >= region_end)
254         uint64_t trim_end  = trim->base + trim->size;
258             trim->base = region_end;
259             trim->size = trim_end - trim->base;
268         region.base = trim_end;
269         region.size = region_end - region.base;
279     // Sanity check.  The number of elements in the base index should match the
299     // Compute the things we will need round-up align base addresses.
305     auto iter = avail_regions_by_size_.lower_bound({ .base = 0, .size = size });
313         aligned_base = (iter->base + mask) & inv_mask;
314         uint64_t overhead = aligned_base - iter->base;
317         // We have a usable region if the aligned base address has not wrapped
321         if ((aligned_base >= iter->base) && (overhead <= leftover))
341     uint64_t base = requested_region.base;
346     if (!size || ((base + size) < base))
349     // Find the first available region whose base address is strictly greater
351     auto iter = avail_regions_by_base_.upper_bound(base);
360     // We know that base must be >= iter->base
362     // Therefore, we know that base is in the range [iter.start, iter.end]
363     // We know that request.end is > base
364     // Therefore request.end is > iter.base
370     ZX_DEBUG_ASSERT(iter->base <= base);
371     uint64_t req_end  = base + size - 1;
372     uint64_t iter_end = iter->base + iter->size - 1;
380     return AllocFromAvailLocked(by_size_iter, out_region, base, size);
391     if ((region.base + region.size) <= region.base)
420                                                   uint64_t base,
424     ZX_DEBUG_ASSERT(base >= source->base);
427     uint64_t overhead = base - source->base;
437     bool split_before = base != source->base;
458         before_region->base = after_region->base;
460         after_region->base += size;
478         after_region->base   = base;
502         region->base        = before_region->base + overhead;
504         after_region->base  = region->base + region->size;
528     auto before = avail_regions_by_base_.upper_bound(region->base);
532     uint64_t region_end = (region->base + region->size);    // exclusive end
534         ZX_DEBUG_ASSERT(before->base <= region->base);
536         uint64_t before_end = (before->base + before->size);    // exclusive end
537         if (allow_overlap ? (before_end >= region->base) : (before_end == region->base)) {
539             region->base = before->base;
551         ZX_DEBUG_ASSERT(region->base < after->base);
553         if (!(allow_overlap ? (region_end >= after->base) : (region_end == after->base)))
556         uint64_t after_end = (after->base + after->size);
572     region->size = region_end - region->base;
579     // Find the first entry in the tree whose base is >= region.base.  If this
580     // element exists, and its base is < the exclusive end of region, then
582     auto iter = tree.lower_bound(region.base);
583     if (iter.IsValid() && (iter->base < (region.base + region.size)))
587     // base is < region.base.  If it's exclusive end is >= region.base, then we
590     if (iter.IsValid() && (region.base < (iter->base + iter->size)))