Lines Matching full:node
79 * steep cliff not a real concern. Removing a node again is O(1).
107 static noinline void save_stack(struct drm_mm_node *node) in save_stack() argument
115 node->stack = stack_depot_save(entries, n, GFP_NOWAIT); in save_stack()
120 struct drm_mm_node *node; in show_leaks() local
129 list_for_each_entry(node, drm_mm_nodes(mm), node_list) { in show_leaks()
130 if (!node->stack) { in show_leaks()
131 DRM_ERROR("node [%08llx + %08llx]: unknown owner\n", in show_leaks()
132 node->start, node->size); in show_leaks()
136 nr_entries = stack_depot_fetch(node->stack, &entries); in show_leaks()
138 DRM_ERROR("node [%08llx + %08llx]: inserted at\n%s", in show_leaks()
139 node->start, node->size, buf); in show_leaks()
148 static void save_stack(struct drm_mm_node *node) { } in save_stack() argument
152 #define START(node) ((node)->start) argument
153 #define LAST(node) ((node)->start + (node)->size - 1) argument
168 struct drm_mm_node *node) in drm_mm_interval_tree_add_node() argument
175 node->__subtree_last = LAST(node); in drm_mm_interval_tree_add_node()
181 if (parent->__subtree_last >= node->__subtree_last) in drm_mm_interval_tree_add_node()
184 parent->__subtree_last = node->__subtree_last; in drm_mm_interval_tree_add_node()
200 if (parent->__subtree_last < node->__subtree_last) in drm_mm_interval_tree_add_node()
201 parent->__subtree_last = node->__subtree_last; in drm_mm_interval_tree_add_node()
202 if (node->start < parent->start) { in drm_mm_interval_tree_add_node()
210 rb_link_node(&node->rb, rb, link); in drm_mm_interval_tree_add_node()
211 rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, in drm_mm_interval_tree_add_node()
215 #define HOLE_SIZE(NODE) ((NODE)->hole_size) argument
216 #define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE)) argument
224 struct drm_mm_node *node) in insert_hole_size() argument
227 u64 x = node->hole_size; in insert_hole_size()
240 rb_link_node(&node->rb_hole_size, rb, link); in insert_hole_size()
241 rb_insert_color_cached(&node->rb_hole_size, root, first); in insert_hole_size()
248 static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node) in RB_DECLARE_CALLBACKS_MAX()
251 u64 start = HOLE_ADDR(node), subtree_max_hole = node->subtree_max_hole; in RB_DECLARE_CALLBACKS_MAX()
265 rb_link_node(&node->rb_hole_addr, rb_parent, link); in RB_DECLARE_CALLBACKS_MAX()
266 rb_insert_augmented(&node->rb_hole_addr, root, &augment_callbacks); in RB_DECLARE_CALLBACKS_MAX()
269 static void add_hole(struct drm_mm_node *node) in add_hole() argument
271 struct drm_mm *mm = node->mm; in add_hole()
273 node->hole_size = in add_hole()
274 __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node); in add_hole()
275 node->subtree_max_hole = node->hole_size; in add_hole()
276 DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); in add_hole()
278 insert_hole_size(&mm->holes_size, node); in add_hole()
279 insert_hole_addr(&mm->holes_addr, node); in add_hole()
281 list_add(&node->hole_stack, &mm->hole_stack); in add_hole()
284 static void rm_hole(struct drm_mm_node *node) in rm_hole() argument
286 DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); in rm_hole()
288 list_del(&node->hole_stack); in rm_hole()
289 rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size); in rm_hole()
290 rb_erase_augmented(&node->rb_hole_addr, &node->mm->holes_addr, in rm_hole()
292 node->hole_size = 0; in rm_hole()
293 node->subtree_max_hole = 0; in rm_hole()
295 DRM_MM_BUG_ON(drm_mm_hole_follows(node)); in rm_hole()
314 struct drm_mm_node *node = in best_hole() local
317 if (size <= node->hole_size) { in best_hole()
318 best = node; in best_hole()
336 struct drm_mm_node *node = NULL; in find_hole_addr() local
344 node = rb_hole_addr_to_node(rb); in find_hole_addr()
345 hole_start = __drm_mm_hole_node_start(node); in find_hole_addr()
348 rb = node->rb_hole_addr.rb_left; in find_hole_addr()
349 else if (addr > hole_start + node->hole_size) in find_hole_addr()
350 rb = node->rb_hole_addr.rb_right; in find_hole_addr()
355 return node; in find_hole_addr()
395 struct rb_node *parent, *node = &entry->rb_hole_addr; \
397 if (!entry || RB_EMPTY_NODE(node)) \
400 if (usable_hole_addr(node->first, size)) { \
401 node = node->first; \
402 while (usable_hole_addr(node->last, size)) \
403 node = node->last; \
404 return rb_hole_addr_to_node(node); \
407 while ((parent = rb_parent(node)) && node == parent->first) \
408 node = parent; \
418 struct drm_mm_node *node, in DECLARE_NEXT_HOLE_ADDR()
425 return rb_hole_size_to_node(rb_prev(&node->rb_hole_size)); in DECLARE_NEXT_HOLE_ADDR()
428 return next_hole_low_addr(node, size); in DECLARE_NEXT_HOLE_ADDR()
431 return next_hole_high_addr(node, size); in DECLARE_NEXT_HOLE_ADDR()
434 node = list_next_entry(node, hole_stack); in DECLARE_NEXT_HOLE_ADDR()
435 return &node->hole_stack == &mm->hole_stack ? NULL : node; in DECLARE_NEXT_HOLE_ADDR()
440 * drm_mm_reserve_node - insert an pre-initialized node
441 * @mm: drm_mm allocator to insert @node into
442 * @node: drm_mm_node to insert
451 * 0 on success, -ENOSPC if there's no hole where @node is.
453 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) in drm_mm_reserve_node() argument
460 end = node->start + node->size; in drm_mm_reserve_node()
461 if (unlikely(end <= node->start)) in drm_mm_reserve_node()
464 /* Find the relevant hole to add our node to */ in drm_mm_reserve_node()
465 hole = find_hole_addr(mm, node->start, 0); in drm_mm_reserve_node()
473 mm->color_adjust(hole, node->color, &adj_start, &adj_end); in drm_mm_reserve_node()
475 if (adj_start > node->start || adj_end < end) in drm_mm_reserve_node()
478 node->mm = mm; in drm_mm_reserve_node()
480 __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); in drm_mm_reserve_node()
481 list_add(&node->node_list, &hole->node_list); in drm_mm_reserve_node()
482 drm_mm_interval_tree_add_node(hole, node); in drm_mm_reserve_node()
483 node->hole_size = 0; in drm_mm_reserve_node()
486 if (node->start > hole_start) in drm_mm_reserve_node()
489 add_hole(node); in drm_mm_reserve_node()
491 save_stack(node); in drm_mm_reserve_node()
502 * drm_mm_insert_node_in_range - ranged search for space and insert @node
504 * @node: preallocate node to insert
507 * @color: opaque tag value to use for this node
508 * @range_start: start of the allowed range for this node
509 * @range_end: end of the allowed range for this node
512 * The preallocated @node must be cleared to 0.
518 struct drm_mm_node * const node, in drm_mm_insert_node_in_range() argument
593 node->mm = mm; in drm_mm_insert_node_in_range()
594 node->size = size; in drm_mm_insert_node_in_range()
595 node->start = adj_start; in drm_mm_insert_node_in_range()
596 node->color = color; in drm_mm_insert_node_in_range()
597 node->hole_size = 0; in drm_mm_insert_node_in_range()
599 __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); in drm_mm_insert_node_in_range()
600 list_add(&node->node_list, &hole->node_list); in drm_mm_insert_node_in_range()
601 drm_mm_interval_tree_add_node(hole, node); in drm_mm_insert_node_in_range()
607 add_hole(node); in drm_mm_insert_node_in_range()
609 save_stack(node); in drm_mm_insert_node_in_range()
617 static inline bool drm_mm_node_scanned_block(const struct drm_mm_node *node) in drm_mm_node_scanned_block() argument
619 return test_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); in drm_mm_node_scanned_block()
623 * drm_mm_remove_node - Remove a memory node from the allocator.
624 * @node: drm_mm_node to remove
626 * This just removes a node from its drm_mm allocator. The node does not need to
628 * allocator. It is a bug to call this function on a unallocated node.
630 void drm_mm_remove_node(struct drm_mm_node *node) in drm_mm_remove_node() argument
632 struct drm_mm *mm = node->mm; in drm_mm_remove_node()
635 DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); in drm_mm_remove_node()
636 DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); in drm_mm_remove_node()
638 prev_node = list_prev_entry(node, node_list); in drm_mm_remove_node()
640 if (drm_mm_hole_follows(node)) in drm_mm_remove_node()
641 rm_hole(node); in drm_mm_remove_node()
643 drm_mm_interval_tree_remove(node, &mm->interval_tree); in drm_mm_remove_node()
644 list_del(&node->node_list); in drm_mm_remove_node()
650 clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); in drm_mm_remove_node()
715 * since freeing a node is also O(1) the overall complexity is
773 * drm_mm_scan_add_block - add a node to the scan list
775 * @node: drm_mm_node to add
777 * Add a node to the scan list that might be freed to make space for the desired
784 struct drm_mm_node *node) in drm_mm_scan_add_block() argument
792 DRM_MM_BUG_ON(node->mm != mm); in drm_mm_scan_add_block()
793 DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); in drm_mm_scan_add_block()
794 DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); in drm_mm_scan_add_block()
795 __set_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); in drm_mm_scan_add_block()
799 * (distance between the end of our previous node and the start of in drm_mm_scan_add_block()
803 hole = list_prev_entry(node, node_list); in drm_mm_scan_add_block()
804 DRM_MM_BUG_ON(list_next_entry(hole, node_list) != node); in drm_mm_scan_add_block()
805 __list_del_entry(&node->node_list); in drm_mm_scan_add_block()
856 * drm_mm_scan_remove_block - remove a node from the scan list
858 * @node: drm_mm_node to remove
875 struct drm_mm_node *node) in drm_mm_scan_remove_block() argument
879 DRM_MM_BUG_ON(node->mm != scan->mm); in drm_mm_scan_remove_block()
880 DRM_MM_BUG_ON(!drm_mm_node_scanned_block(node)); in drm_mm_scan_remove_block()
881 __clear_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); in drm_mm_scan_remove_block()
883 DRM_MM_BUG_ON(!node->mm->scan_active); in drm_mm_scan_remove_block()
884 node->mm->scan_active--; in drm_mm_scan_remove_block()
886 /* During drm_mm_scan_add_block() we decoupled this node leaving in drm_mm_scan_remove_block()
890 * backwards correctly we check that prev_node->next == node->next, in drm_mm_scan_remove_block()
891 * i.e. both believe the same node should be on the other side of the in drm_mm_scan_remove_block()
894 prev_node = list_prev_entry(node, node_list); in drm_mm_scan_remove_block()
896 list_next_entry(node, node_list)); in drm_mm_scan_remove_block()
897 list_add(&node->node_list, &prev_node->node_list); in drm_mm_scan_remove_block()
899 return (node->start + node->size > scan->hit_start && in drm_mm_scan_remove_block()
900 node->start < scan->hit_end); in drm_mm_scan_remove_block()
913 * A node to evict, or NULL if there are no overlapping nodes.