drm_mm.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551
  1. /**************************************************************************
  2. *
  3. * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA.
  4. * Copyright 2016 Intel Corporation
  5. * All Rights Reserved.
  6. *
  7. * Permission is hereby granted, free of charge, to any person obtaining a
  8. * copy of this software and associated documentation files (the
  9. * "Software"), to deal in the Software without restriction, including
  10. * without limitation the rights to use, copy, modify, merge, publish,
  11. * distribute, sub license, and/or sell copies of the Software, and to
  12. * permit persons to whom the Software is furnished to do so, subject to
  13. * the following conditions:
  14. *
  15. * The above copyright notice and this permission notice (including the
  16. * next paragraph) shall be included in all copies or substantial portions
  17. * of the Software.
  18. *
  19. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21. * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
  22. * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
  23. * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  24. * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  25. * USE OR OTHER DEALINGS IN THE SOFTWARE.
  26. *
  27. *
  28. **************************************************************************/
  29. /*
  30. * Authors:
  31. * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
  32. */
  33. #ifndef _DRM_MM_H_
  34. #define _DRM_MM_H_
  35. /*
  36. * Generic range manager structs
  37. */
  38. #include <linux/bug.h>
  39. #include <linux/rbtree.h>
  40. #include <linux/kernel.h>
  41. #include <linux/mm_types.h>
  42. #include <linux/list.h>
  43. #include <linux/spinlock.h>
  44. #ifdef CONFIG_DRM_DEBUG_MM
  45. #include <linux/stackdepot.h>
  46. #endif
  47. #include <drm/drm_print.h>
  48. #ifdef CONFIG_DRM_DEBUG_MM
  49. #define DRM_MM_BUG_ON(expr) BUG_ON(expr)
  50. #else
  51. #define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr)
  52. #endif
  53. /**
  54. * enum drm_mm_insert_mode - control search and allocation behaviour
  55. *
  56. * The &struct drm_mm range manager supports finding a suitable modes using
  57. * a number of search trees. These trees are oranised by size, by address and
  58. * in most recent eviction order. This allows the user to find either the
  59. * smallest hole to reuse, the lowest or highest address to reuse, or simply
  60. * reuse the most recent eviction that fits. When allocating the &drm_mm_node
  61. * from within the hole, the &drm_mm_insert_mode also dictate whether to
  62. * allocate the lowest matching address or the highest.
  63. */
  64. enum drm_mm_insert_mode {
  65. /**
  66. * @DRM_MM_INSERT_BEST:
  67. *
  68. * Search for the smallest hole (within the search range) that fits
  69. * the desired node.
  70. *
  71. * Allocates the node from the bottom of the found hole.
  72. */
  73. DRM_MM_INSERT_BEST = 0,
  74. /**
  75. * @DRM_MM_INSERT_LOW:
  76. *
  77. * Search for the lowest hole (address closest to 0, within the search
  78. * range) that fits the desired node.
  79. *
  80. * Allocates the node from the bottom of the found hole.
  81. */
  82. DRM_MM_INSERT_LOW,
  83. /**
  84. * @DRM_MM_INSERT_HIGH:
  85. *
  86. * Search for the highest hole (address closest to U64_MAX, within the
  87. * search range) that fits the desired node.
  88. *
  89. * Allocates the node from the *top* of the found hole. The specified
  90. * alignment for the node is applied to the base of the node
  91. * (&drm_mm_node.start).
  92. */
  93. DRM_MM_INSERT_HIGH,
  94. /**
  95. * @DRM_MM_INSERT_EVICT:
  96. *
  97. * Search for the most recently evicted hole (within the search range)
  98. * that fits the desired node. This is appropriate for use immediately
  99. * after performing an eviction scan (see drm_mm_scan_init()) and
  100. * removing the selected nodes to form a hole.
  101. *
  102. * Allocates the node from the bottom of the found hole.
  103. */
  104. DRM_MM_INSERT_EVICT,
  105. /**
  106. * @DRM_MM_INSERT_ONCE:
  107. *
  108. * Only check the first hole for suitablity and report -ENOSPC
  109. * immediately otherwise, rather than check every hole until a
  110. * suitable one is found. Can only be used in conjunction with another
  111. * search method such as DRM_MM_INSERT_HIGH or DRM_MM_INSERT_LOW.
  112. */
  113. DRM_MM_INSERT_ONCE = BIT(31),
  114. /**
  115. * @DRM_MM_INSERT_HIGHEST:
  116. *
  117. * Only check the highest hole (the hole with the largest address) and
  118. * insert the node at the top of the hole or report -ENOSPC if
  119. * unsuitable.
  120. *
  121. * Does not search all holes.
  122. */
  123. DRM_MM_INSERT_HIGHEST = DRM_MM_INSERT_HIGH | DRM_MM_INSERT_ONCE,
  124. /**
  125. * @DRM_MM_INSERT_LOWEST:
  126. *
  127. * Only check the lowest hole (the hole with the smallest address) and
  128. * insert the node at the bottom of the hole or report -ENOSPC if
  129. * unsuitable.
  130. *
  131. * Does not search all holes.
  132. */
  133. DRM_MM_INSERT_LOWEST = DRM_MM_INSERT_LOW | DRM_MM_INSERT_ONCE,
  134. };
  135. /**
  136. * struct drm_mm_node - allocated block in the DRM allocator
  137. *
  138. * This represents an allocated block in a &drm_mm allocator. Except for
  139. * pre-reserved nodes inserted using drm_mm_reserve_node() the structure is
  140. * entirely opaque and should only be accessed through the provided funcions.
  141. * Since allocation of these nodes is entirely handled by the driver they can be
  142. * embedded.
  143. */
  144. struct drm_mm_node {
  145. /** @color: Opaque driver-private tag. */
  146. unsigned long color;
  147. /** @start: Start address of the allocated block. */
  148. u64 start;
  149. /** @size: Size of the allocated block. */
  150. u64 size;
  151. /* private: */
  152. struct drm_mm *mm;
  153. struct list_head node_list;
  154. struct list_head hole_stack;
  155. struct rb_node rb;
  156. struct rb_node rb_hole_size;
  157. struct rb_node rb_hole_addr;
  158. u64 __subtree_last;
  159. u64 hole_size;
  160. u64 subtree_max_hole;
  161. unsigned long flags;
  162. #define DRM_MM_NODE_ALLOCATED_BIT 0
  163. #define DRM_MM_NODE_SCANNED_BIT 1
  164. #ifdef CONFIG_DRM_DEBUG_MM
  165. depot_stack_handle_t stack;
  166. #endif
  167. };
  168. /**
  169. * struct drm_mm - DRM allocator
  170. *
  171. * DRM range allocator with a few special functions and features geared towards
  172. * managing GPU memory. Except for the @color_adjust callback the structure is
  173. * entirely opaque and should only be accessed through the provided functions
  174. * and macros. This structure can be embedded into larger driver structures.
  175. */
  176. struct drm_mm {
  177. /**
  178. * @color_adjust:
  179. *
  180. * Optional driver callback to further apply restrictions on a hole. The
  181. * node argument points at the node containing the hole from which the
  182. * block would be allocated (see drm_mm_hole_follows() and friends). The
  183. * other arguments are the size of the block to be allocated. The driver
  184. * can adjust the start and end as needed to e.g. insert guard pages.
  185. */
  186. void (*color_adjust)(const struct drm_mm_node *node,
  187. unsigned long color,
  188. u64 *start, u64 *end);
  189. /* private: */
  190. /* List of all memory nodes that immediately precede a free hole. */
  191. struct list_head hole_stack;
  192. /* head_node.node_list is the list of all memory nodes, ordered
  193. * according to the (increasing) start address of the memory node. */
  194. struct drm_mm_node head_node;
  195. /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
  196. struct rb_root_cached interval_tree;
  197. struct rb_root_cached holes_size;
  198. struct rb_root holes_addr;
  199. unsigned long scan_active;
  200. };
  201. /**
  202. * struct drm_mm_scan - DRM allocator eviction roaster data
  203. *
  204. * This structure tracks data needed for the eviction roaster set up using
  205. * drm_mm_scan_init(), and used with drm_mm_scan_add_block() and
  206. * drm_mm_scan_remove_block(). The structure is entirely opaque and should only
  207. * be accessed through the provided functions and macros. It is meant to be
  208. * allocated temporarily by the driver on the stack.
  209. */
  210. struct drm_mm_scan {
  211. /* private: */
  212. struct drm_mm *mm;
  213. u64 size;
  214. u64 alignment;
  215. u64 remainder_mask;
  216. u64 range_start;
  217. u64 range_end;
  218. u64 hit_start;
  219. u64 hit_end;
  220. unsigned long color;
  221. enum drm_mm_insert_mode mode;
  222. };
  223. /**
  224. * drm_mm_node_allocated - checks whether a node is allocated
  225. * @node: drm_mm_node to check
  226. *
  227. * Drivers are required to clear a node prior to using it with the
  228. * drm_mm range manager.
  229. *
  230. * Drivers should use this helper for proper encapsulation of drm_mm
  231. * internals.
  232. *
  233. * Returns:
  234. * True if the @node is allocated.
  235. */
  236. static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
  237. {
  238. return test_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
  239. }
  240. /**
  241. * drm_mm_initialized - checks whether an allocator is initialized
  242. * @mm: drm_mm to check
  243. *
  244. * Drivers should clear the struct drm_mm prior to initialisation if they
  245. * want to use this function.
  246. *
  247. * Drivers should use this helper for proper encapsulation of drm_mm
  248. * internals.
  249. *
  250. * Returns:
  251. * True if the @mm is initialized.
  252. */
  253. static inline bool drm_mm_initialized(const struct drm_mm *mm)
  254. {
  255. return READ_ONCE(mm->hole_stack.next);
  256. }
  257. /**
  258. * drm_mm_hole_follows - checks whether a hole follows this node
  259. * @node: drm_mm_node to check
  260. *
  261. * Holes are embedded into the drm_mm using the tail of a drm_mm_node.
  262. * If you wish to know whether a hole follows this particular node,
  263. * query this function. See also drm_mm_hole_node_start() and
  264. * drm_mm_hole_node_end().
  265. *
  266. * Returns:
  267. * True if a hole follows the @node.
  268. */
  269. static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
  270. {
  271. return node->hole_size;
  272. }
  273. static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
  274. {
  275. return hole_node->start + hole_node->size;
  276. }
  277. /**
  278. * drm_mm_hole_node_start - computes the start of the hole following @node
  279. * @hole_node: drm_mm_node which implicitly tracks the following hole
  280. *
  281. * This is useful for driver-specific debug dumpers. Otherwise drivers should
  282. * not inspect holes themselves. Drivers must check first whether a hole indeed
  283. * follows by looking at drm_mm_hole_follows()
  284. *
  285. * Returns:
  286. * Start of the subsequent hole.
  287. */
  288. static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
  289. {
  290. DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
  291. return __drm_mm_hole_node_start(hole_node);
  292. }
  293. static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
  294. {
  295. return list_next_entry(hole_node, node_list)->start;
  296. }
  297. /**
  298. * drm_mm_hole_node_end - computes the end of the hole following @node
  299. * @hole_node: drm_mm_node which implicitly tracks the following hole
  300. *
  301. * This is useful for driver-specific debug dumpers. Otherwise drivers should
  302. * not inspect holes themselves. Drivers must check first whether a hole indeed
  303. * follows by looking at drm_mm_hole_follows().
  304. *
  305. * Returns:
  306. * End of the subsequent hole.
  307. */
  308. static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
  309. {
  310. return __drm_mm_hole_node_end(hole_node);
  311. }
  312. /**
  313. * drm_mm_nodes - list of nodes under the drm_mm range manager
  314. * @mm: the struct drm_mm range manager
  315. *
  316. * As the drm_mm range manager hides its node_list deep with its
  317. * structure, extracting it looks painful and repetitive. This is
  318. * not expected to be used outside of the drm_mm_for_each_node()
  319. * macros and similar internal functions.
  320. *
  321. * Returns:
  322. * The node list, may be empty.
  323. */
  324. #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
  325. /**
  326. * drm_mm_for_each_node - iterator to walk over all allocated nodes
  327. * @entry: &struct drm_mm_node to assign to in each iteration step
  328. * @mm: &drm_mm allocator to walk
  329. *
  330. * This iterator walks over all nodes in the range allocator. It is implemented
  331. * with list_for_each(), so not save against removal of elements.
  332. */
  333. #define drm_mm_for_each_node(entry, mm) \
  334. list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
  335. /**
  336. * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes
  337. * @entry: &struct drm_mm_node to assign to in each iteration step
  338. * @next: &struct drm_mm_node to store the next step
  339. * @mm: &drm_mm allocator to walk
  340. *
  341. * This iterator walks over all nodes in the range allocator. It is implemented
  342. * with list_for_each_safe(), so save against removal of elements.
  343. */
  344. #define drm_mm_for_each_node_safe(entry, next, mm) \
  345. list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
  346. /**
  347. * drm_mm_for_each_hole - iterator to walk over all holes
  348. * @pos: &drm_mm_node used internally to track progress
  349. * @mm: &drm_mm allocator to walk
  350. * @hole_start: ulong variable to assign the hole start to on each iteration
  351. * @hole_end: ulong variable to assign the hole end to on each iteration
  352. *
  353. * This iterator walks over all holes in the range allocator. It is implemented
  354. * with list_for_each(), so not save against removal of elements. @entry is used
  355. * internally and will not reflect a real drm_mm_node for the very first hole.
  356. * Hence users of this iterator may not access it.
  357. *
  358. * Implementation Note:
  359. * We need to inline list_for_each_entry in order to be able to set hole_start
  360. * and hole_end on each iteration while keeping the macro sane.
  361. */
  362. #define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \
  363. for (pos = list_first_entry(&(mm)->hole_stack, \
  364. typeof(*pos), hole_stack); \
  365. &pos->hole_stack != &(mm)->hole_stack ? \
  366. hole_start = drm_mm_hole_node_start(pos), \
  367. hole_end = hole_start + pos->hole_size, \
  368. 1 : 0; \
  369. pos = list_next_entry(pos, hole_stack))
  370. /*
  371. * Basic range manager support (drm_mm.c)
  372. */
  373. int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
  374. int drm_mm_insert_node_in_range(struct drm_mm *mm,
  375. struct drm_mm_node *node,
  376. u64 size,
  377. u64 alignment,
  378. unsigned long color,
  379. u64 start,
  380. u64 end,
  381. enum drm_mm_insert_mode mode);
  382. /**
  383. * drm_mm_insert_node_generic - search for space and insert @node
  384. * @mm: drm_mm to allocate from
  385. * @node: preallocate node to insert
  386. * @size: size of the allocation
  387. * @alignment: alignment of the allocation
  388. * @color: opaque tag value to use for this node
  389. * @mode: fine-tune the allocation search and placement
  390. *
  391. * This is a simplified version of drm_mm_insert_node_in_range() with no
  392. * range restrictions applied.
  393. *
  394. * The preallocated node must be cleared to 0.
  395. *
  396. * Returns:
  397. * 0 on success, -ENOSPC if there's no suitable hole.
  398. */
  399. static inline int
  400. drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
  401. u64 size, u64 alignment,
  402. unsigned long color,
  403. enum drm_mm_insert_mode mode)
  404. {
  405. return drm_mm_insert_node_in_range(mm, node,
  406. size, alignment, color,
  407. 0, U64_MAX, mode);
  408. }
  409. /**
  410. * drm_mm_insert_node - search for space and insert @node
  411. * @mm: drm_mm to allocate from
  412. * @node: preallocate node to insert
  413. * @size: size of the allocation
  414. *
  415. * This is a simplified version of drm_mm_insert_node_generic() with @color set
  416. * to 0.
  417. *
  418. * The preallocated node must be cleared to 0.
  419. *
  420. * Returns:
  421. * 0 on success, -ENOSPC if there's no suitable hole.
  422. */
  423. static inline int drm_mm_insert_node(struct drm_mm *mm,
  424. struct drm_mm_node *node,
  425. u64 size)
  426. {
  427. return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
  428. }
  429. void drm_mm_remove_node(struct drm_mm_node *node);
  430. void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
  431. void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
  432. void drm_mm_takedown(struct drm_mm *mm);
  433. /**
  434. * drm_mm_clean - checks whether an allocator is clean
  435. * @mm: drm_mm allocator to check
  436. *
  437. * Returns:
  438. * True if the allocator is completely free, false if there's still a node
  439. * allocated in it.
  440. */
  441. static inline bool drm_mm_clean(const struct drm_mm *mm)
  442. {
  443. return list_empty(drm_mm_nodes(mm));
  444. }
  445. struct drm_mm_node *
  446. __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
  447. /**
  448. * drm_mm_for_each_node_in_range - iterator to walk over a range of
  449. * allocated nodes
  450. * @node__: drm_mm_node structure to assign to in each iteration step
  451. * @mm__: drm_mm allocator to walk
  452. * @start__: starting offset, the first node will overlap this
  453. * @end__: ending offset, the last node will start before this (but may overlap)
  454. *
  455. * This iterator walks over all nodes in the range allocator that lie
  456. * between @start and @end. It is implemented similarly to list_for_each(),
  457. * but using the internal interval tree to accelerate the search for the
  458. * starting node, and so not safe against removal of elements. It assumes
  459. * that @end is within (or is the upper limit of) the drm_mm allocator.
  460. * If [@start, @end] are beyond the range of the drm_mm, the iterator may walk
  461. * over the special _unallocated_ &drm_mm.head_node, and may even continue
  462. * indefinitely.
  463. */
  464. #define drm_mm_for_each_node_in_range(node__, mm__, start__, end__) \
  465. for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
  466. node__->start < (end__); \
  467. node__ = list_next_entry(node__, node_list))
  468. void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
  469. struct drm_mm *mm,
  470. u64 size, u64 alignment, unsigned long color,
  471. u64 start, u64 end,
  472. enum drm_mm_insert_mode mode);
  473. /**
  474. * drm_mm_scan_init - initialize lru scanning
  475. * @scan: scan state
  476. * @mm: drm_mm to scan
  477. * @size: size of the allocation
  478. * @alignment: alignment of the allocation
  479. * @color: opaque tag value to use for the allocation
  480. * @mode: fine-tune the allocation search and placement
  481. *
  482. * This is a simplified version of drm_mm_scan_init_with_range() with no range
  483. * restrictions applied.
  484. *
  485. * This simply sets up the scanning routines with the parameters for the desired
  486. * hole.
  487. *
  488. * Warning:
  489. * As long as the scan list is non-empty, no other operations than
  490. * adding/removing nodes to/from the scan list are allowed.
  491. */
  492. static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
  493. struct drm_mm *mm,
  494. u64 size,
  495. u64 alignment,
  496. unsigned long color,
  497. enum drm_mm_insert_mode mode)
  498. {
  499. drm_mm_scan_init_with_range(scan, mm,
  500. size, alignment, color,
  501. 0, U64_MAX, mode);
  502. }
  503. bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
  504. struct drm_mm_node *node);
  505. bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
  506. struct drm_mm_node *node);
  507. struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);
  508. void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);
  509. #endif