Lines Matching defs:hole
59 util_vma_foreach_hole_safe(hole, heap)
60 free(hole);
68 util_vma_foreach_hole(hole, heap) {
69 assert(hole->offset > 0);
70 assert(hole->size > 0);
72 if (&hole->link == heap->holes.next) {
73 /* This must be the top-most hole. Assert that, if it overflows, it
76 assert(hole->size + hole->offset == 0 ||
77 hole->size + hole->offset > hole->offset);
79 /* This is not the top-most hole so it must not overflow and, in
80 * fact, must be strictly lower than the top-most hole. If
81 * hole->size + hole->offset == prev_offset, then we failed to join
84 assert(hole->size + hole->offset > hole->offset &&
85 hole->size + hole->offset < prev_offset);
87 prev_offset = hole->offset;
95 util_vma_hole_alloc(struct util_vma_hole *hole,
98 assert(hole->offset <= offset);
99 assert(hole->size >= offset - hole->offset + size);
101 if (offset == hole->offset && size == hole->size) {
102 /* Just get rid of the hole. */
103 list_del(&hole->link);
104 free(hole);
108 assert(offset - hole->offset <= hole->size - size);
109 uint64_t waste = (hole->size - size) - (offset - hole->offset);
111 /* We allocated at the top. Shrink the hole down. */
112 hole->size -= size;
116 if (offset == hole->offset) {
117 /* We allocated at the bottom. Shrink the hole up. */
118 hole->offset += size;
119 hole->size -= size;
123 /* We allocated in the middle. We need to split the old hole into two
126 struct util_vma_hole *high_hole = calloc(1, sizeof(*hole));
130 /* Adjust the hole to be the amount of space left at he bottom of the
131 * original hole.
133 hole->size = offset - hole->offset;
135 /* Place the new hole before the old hole so that the list is in order
138 list_addtail(&high_hole->link, &hole->link);
152 util_vma_foreach_hole_safe(hole, heap) {
153 if (size > hole->size)
157 * given size can be without going over the top of the hole.
160 * hole->size + hole->offset can only overflow to 0 and size > 0.
162 uint64_t offset = (hole->size - size) + hole->offset;
165 * allocating from the top of the hole and not the bottom.
169 if (offset < hole->offset)
172 util_vma_hole_alloc(hole, offset, size);
177 util_vma_foreach_hole_safe_rev(hole, heap) {
178 if (size > hole->size)
181 uint64_t offset = hole->offset;
187 if (pad > hole->size - size)
193 util_vma_hole_alloc(hole, offset, size);
220 /* Find the hole if one exists. */
221 util_vma_foreach_hole_safe(hole, heap) {
222 if (hole->offset > offset)
225 /* Holes are ordered high-to-low so the first hole we find with
226 * hole->offset <= is our hole. If it's not big enough to contain the
229 assert(hole->offset <= offset);
230 if (hole->size < offset - hole->offset + size)
233 util_vma_hole_alloc(hole, offset, size);
237 /* We didn't find a suitable hole */
262 util_vma_foreach_hole(hole, heap) {
263 if (hole->offset <= offset) {
264 low_hole = hole;
267 high_hole = hole;
286 /* Merge into the low hole */
289 /* Merge into the high hole */
293 /* Neither hole is adjacent; make a new one */
294 struct util_vma_hole *hole = calloc(1, sizeof(*hole));
296 hole->offset = offset;
297 hole->size = size;
299 /* Add it after the high hole so we maintain high-to-low ordering */
301 list_add(&hole->link, &high_hole->link);
303 list_add(&hole->link, &heap->holes);
316 util_vma_foreach_hole(hole, heap) {
317 fprintf(fp, "%s hole: offset = %"PRIu64" (0x%"PRIx64", "
319 tab, hole->offset, hole->offset, hole->size, hole->size);
320 total_free += hole->size;