kernel/vm/VMKernelAddressSpace.cpp

56 	\param alignedBase The base address of the range to check.
58 	\param limit The last (inclusive) addresss of the range to check.
106 	Range* range = new(fRangesObjectCache, 0) Range(fBase, size,
108 	if (range == NULL)
111 	_InsertRange(range);
113 	TRACE("VMKernelAddressSpace::InitObject(): address range: %#" B_PRIxADDR
124 	Range* range = fRangeList.Head();
125 	while (range != NULL && range->type != Range::RANGE_AREA)
126 		range = fRangeList.GetNext(range);
127 	return range != NULL ? range->area : NULL;
134 	Range* range = static_cast<VMKernelArea*>(_area)->Range();
136 		range = fRangeList.GetNext(range);
137 	} while (range != NULL && range->type != Range::RANGE_AREA);
138 	return range != NULL ? range->area : NULL;
165 	Range* range = fRangeTree.FindClosest(address, true);
166 	if (range == NULL || range->type != Range::RANGE_AREA)
169 	VMKernelArea* area = range->area;
178 	Range* range = fRangeTree.FindClosest(address, less);
179 	while (range != NULL && range->type != Range::RANGE_AREA)
180 		range = fRangeTree.Next(range);
182 	return range != NULL ? range->area : NULL;
202 	Range* range;
205 		allocationFlags, range);
209 	range->type = Range::RANGE_AREA;
210 	range->area = area;
211 	area->SetRange(range);
212 	area->SetBase(range->base);
213 	area->SetSize(range->size);
244 	Range* range = static_cast<VMKernelArea*>(area)->Range();
246 	if (newSize <= range->size)
249 	Range* nextRange = fRangeList.GetNext(range);
254 		&& nextRange->reserved.base > range->base) {
258 	// TODO: If there is free space after a reserved range (or vice versa), it
260 	return newSize - range->size <= nextRange->size;
272 	Range* range = area->Range();
274 	if (newSize == range->size)
277 	Range* nextRange = fRangeList.GetNext(range);
279 	if (newSize < range->size) {
281 			// a free range is following -- just enlarge it
283 			nextRange->size += range->size - newSize;
284 			nextRange->base = range->base + newSize;
287 			// no free range following -- we need to allocate a new one and
290 				range->base + newSize, range->size - newSize,
299 				&& nextRange->reserved.base > range->base)) {
302 		// TODO: If there is free space after a reserved range (or vice versa),
304 		size_t sizeDiff = newSize - range->size;
309 			// The next range is completely covered -- remove and delete it.
313 			// The next range is only partially covered -- shrink it.
317 			nextRange->base = range->base + newSize;
323 	range->size = newSize;
340 	Range* range = area->Range();
342 	if (newSize == range->size)
345 	if (newSize > range->size)
348 	Range* previousRange = fRangeList.GetPrevious(range);
350 	size_t sizeDiff = range->size - newSize;
352 		// the previous range is free -- just enlarge it
356 		range->base += sizeDiff;
357 		range->size = newSize;
359 		// no free range before -- we need to allocate a new one and
362 			range->base, sizeDiff, Range::RANGE_FREE);
365 		range->base += sizeDiff;
366 		range->size = newSize;
370 	area->SetBase(range->base);
371 	area->SetSize(range->size);
396 	// Don't allow range reservations, if the address space is about to be
401 	Range* range;
403 		allocationFlags, range);
407 	range->type = Range::RANGE_RESERVED;
408 	range->reserved.base = range->base;
409 	range->reserved.flags = flags;
412 		*_address = (void*)range->base;
427 	// Don't allow range unreservations, if the address space is about to be
432 	// search range list and remove any matching reserved ranges
434 	Range* range = fRangeTree.FindClosest(address, false);
435 	while (range != NULL && range->base + (range->size - 1) <= endAddress) {
436 		// Get the next range for the iteration -- we need to skip free ranges,
437 		// since _FreeRange() might join them with the current range and delete
439 		Range* nextRange = fRangeList.GetNext(range);
443 		if (range->type == Range::RANGE_RESERVED) {
444 			_FreeRange(range, allocationFlags);
448 		range = nextRange;
459 	Range* range = fRangeList.Head();
460 	while (range != NULL) {
461 		// Get the next range for the iteration -- we need to skip free ranges,
462 		// since _FreeRange() might join them with the current range and delete
464 		Range* nextRange = fRangeList.GetNext(range);
468 		if (range->type == Range::RANGE_RESERVED) {
469 			_FreeRange(range, allocationFlags);
473 		range = nextRange;
485 	kprintf("range list:\n");
488 			Range* range = it.Next();) {
490 		switch (range->type) {
493 				VMKernelArea* area = range->area;
505 					B_PRIxSIZE " flags = %#" B_PRIx32 "\n", range->base,
506 					range->reserved.base, range->size, range->reserved.flags);
511 					B_PRIxSIZE "\n", range->base, range->size);
519 VMKernelAddressSpace::_FreeListInsertRange(Range* range, size_t size)
522 		", %#" B_PRIxSIZE ", %d), %#" B_PRIxSIZE " (%d))\n", range, range->base,
523 		range->size, range->type, size, ld(size) - PAGE_SHIFT);
525 	fFreeLists[ld(size) - PAGE_SHIFT].Add(range);
530 VMKernelAddressSpace::_FreeListRemoveRange(Range* range, size_t size)
533 		", %#" B_PRIxSIZE ", %d), %#" B_PRIxSIZE " (%d))\n", range, range->base,
534 		range->size, range->type, size, ld(size) - PAGE_SHIFT);
536 	fFreeLists[ld(size) - PAGE_SHIFT].Remove(range);
541 VMKernelAddressSpace::_InsertRange(Range* range)
544 		B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type);
546 	// insert at the correct position in the range list
547 	Range* insertBeforeRange = fRangeTree.FindClosest(range->base, true);
551 		range);
554 	fRangeTree.Insert(range);
556 	// insert in the free ranges list, if the range is free
557 	if (range->type == Range::RANGE_FREE)
558 		_FreeListInsertRange(range, range->size);
563 VMKernelAddressSpace::_RemoveRange(Range* range)
566 		B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type);
568 	// remove from tree and range list
569 	// insert at the correct position in the range list
570 	fRangeTree.Remove(range);
571 	fRangeList.Remove(range);
573 	// if it is a free range, also remove it from the free list
574 	if (range->type == Range::RANGE_FREE)
575 		_FreeListRemoveRange(range, range->size);
590 	// prepare size, alignment and the base address for the range search
624 	// find a range
625 	Range* range = _FindFreeRange(address, size, alignment,
628 	if (range == NULL) {
633 	TRACE("  VMKernelAddressSpace::_AllocateRange() found range:(%p (%#"
634 		B_PRIxADDR ", %#" B_PRIxSIZE ", %d)\n", range, range->base, range->size,
635 		range->type);
637 	// We have found a range. It might not be a perfect fit, in which case
638 	// we have to split the range.
639 	size_t rangeSize = range->size;
641 	if (address == range->base) {
642 		// allocation at the beginning of the range
643 		if (range->size > size) {
644 			// only partial -- split the range
646 				Range(address + size, range->size - size, range);
650 			range->size = size;
653 	} else if (address + size == range->base + range->size) {
654 		// allocation at the end of the range -- split the range
656 			range->base, range->size - size, range);
660 		range->base = address;
661 		range->size = size;
664 		// allocation in the middle of the range -- split the range in three
666 			range->base, address - range->base, range);
670 			address + size, range->size - size - leftOverRange1->size, range);
677 		range->base = address;
678 		range->size = size;
683 	// If the range is a free range, remove it from the respective free list.
684 	if (range->type == Range::RANGE_FREE)
685 		_FreeListRemoveRange(range, rangeSize);
690 		B_PRIxSIZE ")\n", range, range->base, range->size);
692 	_range = range;
710 			// We have to iterate through the range list starting at the given
712 			Range* range = fRangeTree.FindClosest(start, true);
713 			while (range != NULL) {
714 				if (range->type == Range::RANGE_FREE) {
715 					addr_t alignedBase = ROUNDUP(range->base, alignment);
717 							range->base + (range->size - 1))) {
719 						return range;
722 				range = fRangeList.GetNext(range);
725 			// We didn't find a free spot in the requested range, so we'll
737 			// guaranteed to contain the size. Finding a free range is O(1),
747 						Range* range = it.Next();) {
748 					addr_t alignedBase = ROUNDUP(range->base, alignment);
750 							range->base + (range->size - 1))) {
752 						return range;
761 			// for reserved ones, too. Iterate through the range list starting
763 			Range* range = fRangeTree.FindClosest(start, true);
764 			while (range != NULL) {
765 				if (range->type == Range::RANGE_RESERVED) {
766 					addr_t alignedBase = ROUNDUP(range->base, alignment);
768 							range->base + (range->size - 1))) {
771 						if ((range->reserved.flags & RESERVED_AVOID_BASE)
774 								range->base + (range->size - size), alignment);
778 						return range;
781 				range = fRangeList.GetNext(range);
789 			Range* range = fRangeTree.FindClosest(start, true);
790 TRACE("    B_EXACT_ADDRESS: range: %p\n", range);
791 			if (range == NULL || range->type == Range::RANGE_AREA
792 				|| range->base + (range->size - 1) < start + (size - 1)) {
793 				// TODO: Support allocating if the area range covers multiple
795 TRACE("    -> no suitable range\n");
799 			if (range->type != Range::RANGE_FREE && !allowReservedRange)
801 TRACE("    -> reserved range not allowed\n");
806 			return range;
816 VMKernelAddressSpace::_FreeRange(Range* range, uint32 allocationFlags)
819 		B_PRIxSIZE ", %d))\n", range, range->base, range->size, range->type);
823 	Range* previousRange = fRangeList.GetPrevious(range);
824 	Range* nextRange = fRangeList.GetNext(range);
830 			_RemoveRange(range);
832 			previousRange->size += range->size + nextRange->size;
833 			object_cache_delete(fRangesObjectCache, range, allocationFlags);
837 			// join with the previous range only, delete the supplied one
839 			_RemoveRange(range);
840 			previousRange->size += range->size;
841 			object_cache_delete(fRangesObjectCache, range, allocationFlags);
846 			// join with the next range and delete it
848 			range->size += nextRange->size;
852 		// mark the range free and add it to the respective free list
853 		range->type = Range::RANGE_FREE;
854 		_FreeListInsertRange(range, range->size);
869 	// check range list and tree
879 		Range* range = listIt.Next();
881 		if (range != treeRange) {
882 			panic("VMKernelAddressSpace::_CheckStructures(): list/tree range "
883 				"mismatch: %p vs %p", range, treeRange);
885 		if (range == NULL)
888 		if (range->base != nextBase) {
889 			panic("VMKernelAddressSpace::_CheckStructures(): range base %#"
890 				B_PRIxADDR ", expected: %#" B_PRIxADDR, range->base, nextBase);
893 		if (range->size == 0) {
894 			panic("VMKernelAddressSpace::_CheckStructures(): empty range %p",
895 				range);
898 		if (range->size % B_PAGE_SIZE != 0) {
899 			panic("VMKernelAddressSpace::_CheckStructures(): range %p (%#"
900 				B_PRIxADDR ", %#" B_PRIxSIZE ") not page aligned", range,
901 				range->base, range->size);
904 		if (range->size > spaceSize - (range->base - fBase)) {
905 			panic("VMKernelAddressSpace::_CheckStructures(): range too large: "
907 				B_PRIxADDR, range->base, range->size, fEndAddress);
910 		if (range->type == Range::RANGE_FREE) {
917 					previousRange->base, previousRange->size, range,
918 					range->base, range->size);
922 		previousRange = range;
923 		nextBase = range->base + range->size;
924 		previousRangeType = range->type;
941 				Range* range = it.Next();) {
942 			if (range->type != Range::RANGE_FREE) {
944 					"range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in "
945 					"free list %d", range, range->base, range->size,
946 					range->type, i);
949 			if (fRangeTree.Find(range->base) != range) {
951 					"range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in "
952 					"free list %d", range, range->base, range->size,
953 					range->type, i);
956 			if (ld(range->size) - PAGE_SHIFT != i) {
958 					"range %p (%#" B_PRIxADDR ", %#" B_PRIxSIZE ", %d) in "
959 					"wrong free list %d", range, range->base, range->size,
960 					range->type, i);