drm_mm.c 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041
  1. /**************************************************************************
  2. *
  3. * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., 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. * Generic simple memory manager implementation. Intended to be used as a base
  31. * class implementation for more advanced memory managers.
  32. *
  33. * Note that the algorithm used is quite simple and there might be substantial
  34. * performance gains if a smarter free list is implemented. Currently it is
  35. * just an unordered stack of free regions. This could easily be improved if
  36. * an RB-tree is used instead. At least if we expect heavy fragmentation.
  37. *
  38. * Aligned allocations can also see improvement.
  39. *
  40. * Authors:
  41. * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
  42. */
  43. #include <linux/export.h>
  44. #include <linux/interval_tree_generic.h>
  45. #include <linux/seq_file.h>
  46. #include <linux/slab.h>
  47. #include <linux/stacktrace.h>
  48. #include <drm/drm_mm.h>
  49. /**
  50. * DOC: Overview
  51. *
  52. * drm_mm provides a simple range allocator. The drivers are free to use the
  53. * resource allocator from the linux core if it suits them, the upside of drm_mm
  54. * is that it's in the DRM core. Which means that it's easier to extend for
  55. * some of the crazier special purpose needs of gpus.
  56. *
  57. * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node.
  58. * Drivers are free to embed either of them into their own suitable
  59. * datastructures. drm_mm itself will not do any memory allocations of its own,
  60. * so if drivers choose not to embed nodes they need to still allocate them
  61. * themselves.
  62. *
  63. * The range allocator also supports reservation of preallocated blocks. This is
  64. * useful for taking over initial mode setting configurations from the firmware,
  65. * where an object needs to be created which exactly matches the firmware's
  66. * scanout target. As long as the range is still free it can be inserted anytime
  67. * after the allocator is initialized, which helps with avoiding looped
  68. * dependencies in the driver load sequence.
  69. *
  70. * drm_mm maintains a stack of most recently freed holes, which of all
  71. * simplistic datastructures seems to be a fairly decent approach to clustering
  72. * allocations and avoiding too much fragmentation. This means free space
  73. * searches are O(num_holes). Given that all the fancy features drm_mm supports
  74. * something better would be fairly complex and since gfx thrashing is a fairly
  75. * steep cliff not a real concern. Removing a node again is O(1).
  76. *
  77. * drm_mm supports a few features: Alignment and range restrictions can be
  78. * supplied. Furthermore every &drm_mm_node has a color value (which is just an
  79. * opaque unsigned long) which in conjunction with a driver callback can be used
  80. * to implement sophisticated placement restrictions. The i915 DRM driver uses
  81. * this to implement guard pages between incompatible caching domains in the
  82. * graphics TT.
  83. *
  84. * Two behaviors are supported for searching and allocating: bottom-up and
  85. * top-down. The default is bottom-up. Top-down allocation can be used if the
  86. * memory area has different restrictions, or just to reduce fragmentation.
  87. *
  88. * Finally iteration helpers to walk all nodes and all holes are provided as are
  89. * some basic allocator dumpers for debugging.
  90. *
  91. * Note that this range allocator is not thread-safe, drivers need to protect
  92. * modifications with their own locking. The idea behind this is that for a full
  93. * memory manager additional data needs to be protected anyway, hence internal
  94. * locking would be fully redundant.
  95. */
  96. #ifdef CONFIG_DRM_DEBUG_MM
  97. #include <linux/stackdepot.h>
  98. #define STACKDEPTH 32
  99. #define BUFSZ 4096
  100. static noinline void save_stack(struct drm_mm_node *node)
  101. {
  102. unsigned long entries[STACKDEPTH];
  103. unsigned int n;
  104. n = stack_trace_save(entries, ARRAY_SIZE(entries), 1);
  105. /* May be called under spinlock, so avoid sleeping */
  106. node->stack = stack_depot_save(entries, n, GFP_NOWAIT);
  107. }
  108. static void show_leaks(struct drm_mm *mm)
  109. {
  110. struct drm_mm_node *node;
  111. char *buf;
  112. buf = kmalloc(BUFSZ, GFP_KERNEL);
  113. if (!buf)
  114. return;
  115. list_for_each_entry(node, drm_mm_nodes(mm), node_list) {
  116. if (!node->stack) {
  117. DRM_ERROR("node [%08llx + %08llx]: unknown owner\n",
  118. node->start, node->size);
  119. continue;
  120. }
  121. stack_depot_snprint(node->stack, buf, BUFSZ, 0);
  122. DRM_ERROR("node [%08llx + %08llx]: inserted at\n%s",
  123. node->start, node->size, buf);
  124. }
  125. kfree(buf);
  126. }
  127. #undef STACKDEPTH
  128. #undef BUFSZ
  129. #else
  130. static void save_stack(struct drm_mm_node *node) { }
  131. static void show_leaks(struct drm_mm *mm) { }
  132. #endif
  133. #define START(node) ((node)->start)
  134. #define LAST(node) ((node)->start + (node)->size - 1)
  135. INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
  136. u64, __subtree_last,
  137. START, LAST, static inline, drm_mm_interval_tree)
  138. struct drm_mm_node *
  139. __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last)
  140. {
  141. return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree,
  142. start, last) ?: (struct drm_mm_node *)&mm->head_node;
  143. }
  144. EXPORT_SYMBOL(__drm_mm_interval_first);
  145. static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
  146. struct drm_mm_node *node)
  147. {
  148. struct drm_mm *mm = hole_node->mm;
  149. struct rb_node **link, *rb;
  150. struct drm_mm_node *parent;
  151. bool leftmost;
  152. node->__subtree_last = LAST(node);
  153. if (drm_mm_node_allocated(hole_node)) {
  154. rb = &hole_node->rb;
  155. while (rb) {
  156. parent = rb_entry(rb, struct drm_mm_node, rb);
  157. if (parent->__subtree_last >= node->__subtree_last)
  158. break;
  159. parent->__subtree_last = node->__subtree_last;
  160. rb = rb_parent(rb);
  161. }
  162. rb = &hole_node->rb;
  163. link = &hole_node->rb.rb_right;
  164. leftmost = false;
  165. } else {
  166. rb = NULL;
  167. link = &mm->interval_tree.rb_root.rb_node;
  168. leftmost = true;
  169. }
  170. while (*link) {
  171. rb = *link;
  172. parent = rb_entry(rb, struct drm_mm_node, rb);
  173. if (parent->__subtree_last < node->__subtree_last)
  174. parent->__subtree_last = node->__subtree_last;
  175. if (node->start < parent->start) {
  176. link = &parent->rb.rb_left;
  177. } else {
  178. link = &parent->rb.rb_right;
  179. leftmost = false;
  180. }
  181. }
  182. rb_link_node(&node->rb, rb, link);
  183. rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost,
  184. &drm_mm_interval_tree_augment);
  185. }
  186. #define HOLE_SIZE(NODE) ((NODE)->hole_size)
  187. #define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE))
  188. static u64 rb_to_hole_size(struct rb_node *rb)
  189. {
  190. return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
  191. }
  192. static void insert_hole_size(struct rb_root_cached *root,
  193. struct drm_mm_node *node)
  194. {
  195. struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
  196. u64 x = node->hole_size;
  197. bool first = true;
  198. while (*link) {
  199. rb = *link;
  200. if (x > rb_to_hole_size(rb)) {
  201. link = &rb->rb_left;
  202. } else {
  203. link = &rb->rb_right;
  204. first = false;
  205. }
  206. }
  207. rb_link_node(&node->rb_hole_size, rb, link);
  208. rb_insert_color_cached(&node->rb_hole_size, root, first);
  209. }
  210. RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
  211. struct drm_mm_node, rb_hole_addr,
  212. u64, subtree_max_hole, HOLE_SIZE)
  213. static void insert_hole_addr(struct rb_root *root, struct drm_mm_node *node)
  214. {
  215. struct rb_node **link = &root->rb_node, *rb_parent = NULL;
  216. u64 start = HOLE_ADDR(node), subtree_max_hole = node->subtree_max_hole;
  217. struct drm_mm_node *parent;
  218. while (*link) {
  219. rb_parent = *link;
  220. parent = rb_entry(rb_parent, struct drm_mm_node, rb_hole_addr);
  221. if (parent->subtree_max_hole < subtree_max_hole)
  222. parent->subtree_max_hole = subtree_max_hole;
  223. if (start < HOLE_ADDR(parent))
  224. link = &parent->rb_hole_addr.rb_left;
  225. else
  226. link = &parent->rb_hole_addr.rb_right;
  227. }
  228. rb_link_node(&node->rb_hole_addr, rb_parent, link);
  229. rb_insert_augmented(&node->rb_hole_addr, root, &augment_callbacks);
  230. }
  231. static void add_hole(struct drm_mm_node *node)
  232. {
  233. struct drm_mm *mm = node->mm;
  234. node->hole_size =
  235. __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node);
  236. node->subtree_max_hole = node->hole_size;
  237. DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
  238. insert_hole_size(&mm->holes_size, node);
  239. insert_hole_addr(&mm->holes_addr, node);
  240. list_add(&node->hole_stack, &mm->hole_stack);
  241. }
  242. static void rm_hole(struct drm_mm_node *node)
  243. {
  244. DRM_MM_BUG_ON(!drm_mm_hole_follows(node));
  245. list_del(&node->hole_stack);
  246. rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size);
  247. rb_erase_augmented(&node->rb_hole_addr, &node->mm->holes_addr,
  248. &augment_callbacks);
  249. node->hole_size = 0;
  250. node->subtree_max_hole = 0;
  251. DRM_MM_BUG_ON(drm_mm_hole_follows(node));
  252. }
  253. static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb)
  254. {
  255. return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size);
  256. }
  257. static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb)
  258. {
  259. return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr);
  260. }
  261. static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size)
  262. {
  263. struct rb_node *rb = mm->holes_size.rb_root.rb_node;
  264. struct drm_mm_node *best = NULL;
  265. do {
  266. struct drm_mm_node *node =
  267. rb_entry(rb, struct drm_mm_node, rb_hole_size);
  268. if (size <= node->hole_size) {
  269. best = node;
  270. rb = rb->rb_right;
  271. } else {
  272. rb = rb->rb_left;
  273. }
  274. } while (rb);
  275. return best;
  276. }
  277. static bool usable_hole_addr(struct rb_node *rb, u64 size)
  278. {
  279. return rb && rb_hole_addr_to_node(rb)->subtree_max_hole >= size;
  280. }
  281. static struct drm_mm_node *find_hole_addr(struct drm_mm *mm, u64 addr, u64 size)
  282. {
  283. struct rb_node *rb = mm->holes_addr.rb_node;
  284. struct drm_mm_node *node = NULL;
  285. while (rb) {
  286. u64 hole_start;
  287. if (!usable_hole_addr(rb, size))
  288. break;
  289. node = rb_hole_addr_to_node(rb);
  290. hole_start = __drm_mm_hole_node_start(node);
  291. if (addr < hole_start)
  292. rb = node->rb_hole_addr.rb_left;
  293. else if (addr > hole_start + node->hole_size)
  294. rb = node->rb_hole_addr.rb_right;
  295. else
  296. break;
  297. }
  298. return node;
  299. }
  300. static struct drm_mm_node *
  301. first_hole(struct drm_mm *mm,
  302. u64 start, u64 end, u64 size,
  303. enum drm_mm_insert_mode mode)
  304. {
  305. switch (mode) {
  306. default:
  307. case DRM_MM_INSERT_BEST:
  308. return best_hole(mm, size);
  309. case DRM_MM_INSERT_LOW:
  310. return find_hole_addr(mm, start, size);
  311. case DRM_MM_INSERT_HIGH:
  312. return find_hole_addr(mm, end, size);
  313. case DRM_MM_INSERT_EVICT:
  314. return list_first_entry_or_null(&mm->hole_stack,
  315. struct drm_mm_node,
  316. hole_stack);
  317. }
  318. }
  319. /**
  320. * DECLARE_NEXT_HOLE_ADDR - macro to declare next hole functions
  321. * @name: name of function to declare
  322. * @first: first rb member to traverse (either rb_left or rb_right).
  323. * @last: last rb member to traverse (either rb_right or rb_left).
  324. *
  325. * This macro declares a function to return the next hole of the addr rb tree.
  326. * While traversing the tree we take the searched size into account and only
  327. * visit branches with potential big enough holes.
  328. */
  329. #define DECLARE_NEXT_HOLE_ADDR(name, first, last) \
  330. static struct drm_mm_node *name(struct drm_mm_node *entry, u64 size) \
  331. { \
  332. struct rb_node *parent, *node = &entry->rb_hole_addr; \
  333. \
  334. if (!entry || RB_EMPTY_NODE(node)) \
  335. return NULL; \
  336. \
  337. if (usable_hole_addr(node->first, size)) { \
  338. node = node->first; \
  339. while (usable_hole_addr(node->last, size)) \
  340. node = node->last; \
  341. return rb_hole_addr_to_node(node); \
  342. } \
  343. \
  344. while ((parent = rb_parent(node)) && node == parent->first) \
  345. node = parent; \
  346. \
  347. return rb_hole_addr_to_node(parent); \
  348. }
  349. DECLARE_NEXT_HOLE_ADDR(next_hole_high_addr, rb_left, rb_right)
  350. DECLARE_NEXT_HOLE_ADDR(next_hole_low_addr, rb_right, rb_left)
  351. static struct drm_mm_node *
  352. next_hole(struct drm_mm *mm,
  353. struct drm_mm_node *node,
  354. u64 size,
  355. enum drm_mm_insert_mode mode)
  356. {
  357. switch (mode) {
  358. default:
  359. case DRM_MM_INSERT_BEST:
  360. return rb_hole_size_to_node(rb_prev(&node->rb_hole_size));
  361. case DRM_MM_INSERT_LOW:
  362. return next_hole_low_addr(node, size);
  363. case DRM_MM_INSERT_HIGH:
  364. return next_hole_high_addr(node, size);
  365. case DRM_MM_INSERT_EVICT:
  366. node = list_next_entry(node, hole_stack);
  367. return &node->hole_stack == &mm->hole_stack ? NULL : node;
  368. }
  369. }
  370. /**
  371. * drm_mm_reserve_node - insert an pre-initialized node
  372. * @mm: drm_mm allocator to insert @node into
  373. * @node: drm_mm_node to insert
  374. *
  375. * This functions inserts an already set-up &drm_mm_node into the allocator,
  376. * meaning that start, size and color must be set by the caller. All other
  377. * fields must be cleared to 0. This is useful to initialize the allocator with
  378. * preallocated objects which must be set-up before the range allocator can be
  379. * set-up, e.g. when taking over a firmware framebuffer.
  380. *
  381. * Returns:
  382. * 0 on success, -ENOSPC if there's no hole where @node is.
  383. */
  384. int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
  385. {
  386. struct drm_mm_node *hole;
  387. u64 hole_start, hole_end;
  388. u64 adj_start, adj_end;
  389. u64 end;
  390. end = node->start + node->size;
  391. if (unlikely(end <= node->start))
  392. return -ENOSPC;
  393. /* Find the relevant hole to add our node to */
  394. hole = find_hole_addr(mm, node->start, 0);
  395. if (!hole)
  396. return -ENOSPC;
  397. adj_start = hole_start = __drm_mm_hole_node_start(hole);
  398. adj_end = hole_end = hole_start + hole->hole_size;
  399. if (mm->color_adjust)
  400. mm->color_adjust(hole, node->color, &adj_start, &adj_end);
  401. if (adj_start > node->start || adj_end < end)
  402. return -ENOSPC;
  403. node->mm = mm;
  404. __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
  405. list_add(&node->node_list, &hole->node_list);
  406. drm_mm_interval_tree_add_node(hole, node);
  407. node->hole_size = 0;
  408. rm_hole(hole);
  409. if (node->start > hole_start)
  410. add_hole(hole);
  411. if (end < hole_end)
  412. add_hole(node);
  413. save_stack(node);
  414. return 0;
  415. }
  416. EXPORT_SYMBOL(drm_mm_reserve_node);
  417. static u64 rb_to_hole_size_or_zero(struct rb_node *rb)
  418. {
  419. return rb ? rb_to_hole_size(rb) : 0;
  420. }
  421. /**
  422. * drm_mm_insert_node_in_range - ranged search for space and insert @node
  423. * @mm: drm_mm to allocate from
  424. * @node: preallocate node to insert
  425. * @size: size of the allocation
  426. * @alignment: alignment of the allocation
  427. * @color: opaque tag value to use for this node
  428. * @range_start: start of the allowed range for this node
  429. * @range_end: end of the allowed range for this node
  430. * @mode: fine-tune the allocation search and placement
  431. *
  432. * The preallocated @node must be cleared to 0.
  433. *
  434. * Returns:
  435. * 0 on success, -ENOSPC if there's no suitable hole.
  436. */
  437. int drm_mm_insert_node_in_range(struct drm_mm * const mm,
  438. struct drm_mm_node * const node,
  439. u64 size, u64 alignment,
  440. unsigned long color,
  441. u64 range_start, u64 range_end,
  442. enum drm_mm_insert_mode mode)
  443. {
  444. struct drm_mm_node *hole;
  445. u64 remainder_mask;
  446. bool once;
  447. DRM_MM_BUG_ON(range_start > range_end);
  448. if (unlikely(size == 0 || range_end - range_start < size))
  449. return -ENOSPC;
  450. if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size)
  451. return -ENOSPC;
  452. if (alignment <= 1)
  453. alignment = 0;
  454. once = mode & DRM_MM_INSERT_ONCE;
  455. mode &= ~DRM_MM_INSERT_ONCE;
  456. remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
  457. for (hole = first_hole(mm, range_start, range_end, size, mode);
  458. hole;
  459. hole = once ? NULL : next_hole(mm, hole, size, mode)) {
  460. u64 hole_start = __drm_mm_hole_node_start(hole);
  461. u64 hole_end = hole_start + hole->hole_size;
  462. u64 adj_start, adj_end;
  463. u64 col_start, col_end;
  464. if (mode == DRM_MM_INSERT_LOW && hole_start >= range_end)
  465. break;
  466. if (mode == DRM_MM_INSERT_HIGH && hole_end <= range_start)
  467. break;
  468. col_start = hole_start;
  469. col_end = hole_end;
  470. if (mm->color_adjust)
  471. mm->color_adjust(hole, color, &col_start, &col_end);
  472. adj_start = max(col_start, range_start);
  473. adj_end = min(col_end, range_end);
  474. if (adj_end <= adj_start || adj_end - adj_start < size)
  475. continue;
  476. if (mode == DRM_MM_INSERT_HIGH)
  477. adj_start = adj_end - size;
  478. if (alignment) {
  479. u64 rem;
  480. if (likely(remainder_mask))
  481. rem = adj_start & remainder_mask;
  482. else
  483. div64_u64_rem(adj_start, alignment, &rem);
  484. if (rem) {
  485. adj_start -= rem;
  486. if (mode != DRM_MM_INSERT_HIGH)
  487. adj_start += alignment;
  488. if (adj_start < max(col_start, range_start) ||
  489. min(col_end, range_end) - adj_start < size)
  490. continue;
  491. if (adj_end <= adj_start ||
  492. adj_end - adj_start < size)
  493. continue;
  494. }
  495. }
  496. node->mm = mm;
  497. node->size = size;
  498. node->start = adj_start;
  499. node->color = color;
  500. node->hole_size = 0;
  501. __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
  502. list_add(&node->node_list, &hole->node_list);
  503. drm_mm_interval_tree_add_node(hole, node);
  504. rm_hole(hole);
  505. if (adj_start > hole_start)
  506. add_hole(hole);
  507. if (adj_start + size < hole_end)
  508. add_hole(node);
  509. save_stack(node);
  510. return 0;
  511. }
  512. return -ENOSPC;
  513. }
  514. EXPORT_SYMBOL(drm_mm_insert_node_in_range);
  515. static inline bool drm_mm_node_scanned_block(const struct drm_mm_node *node)
  516. {
  517. return test_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
  518. }
  519. /**
  520. * drm_mm_remove_node - Remove a memory node from the allocator.
  521. * @node: drm_mm_node to remove
  522. *
  523. * This just removes a node from its drm_mm allocator. The node does not need to
  524. * be cleared again before it can be re-inserted into this or any other drm_mm
  525. * allocator. It is a bug to call this function on a unallocated node.
  526. */
  527. void drm_mm_remove_node(struct drm_mm_node *node)
  528. {
  529. struct drm_mm *mm = node->mm;
  530. struct drm_mm_node *prev_node;
  531. DRM_MM_BUG_ON(!drm_mm_node_allocated(node));
  532. DRM_MM_BUG_ON(drm_mm_node_scanned_block(node));
  533. prev_node = list_prev_entry(node, node_list);
  534. if (drm_mm_hole_follows(node))
  535. rm_hole(node);
  536. drm_mm_interval_tree_remove(node, &mm->interval_tree);
  537. list_del(&node->node_list);
  538. if (drm_mm_hole_follows(prev_node))
  539. rm_hole(prev_node);
  540. add_hole(prev_node);
  541. clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
  542. }
  543. EXPORT_SYMBOL(drm_mm_remove_node);
  544. /**
  545. * drm_mm_replace_node - move an allocation from @old to @new
  546. * @old: drm_mm_node to remove from the allocator
  547. * @new: drm_mm_node which should inherit @old's allocation
  548. *
  549. * This is useful for when drivers embed the drm_mm_node structure and hence
  550. * can't move allocations by reassigning pointers. It's a combination of remove
  551. * and insert with the guarantee that the allocation start will match.
  552. */
  553. void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
  554. {
  555. struct drm_mm *mm = old->mm;
  556. DRM_MM_BUG_ON(!drm_mm_node_allocated(old));
  557. *new = *old;
  558. __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &new->flags);
  559. list_replace(&old->node_list, &new->node_list);
  560. rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree);
  561. if (drm_mm_hole_follows(old)) {
  562. list_replace(&old->hole_stack, &new->hole_stack);
  563. rb_replace_node_cached(&old->rb_hole_size,
  564. &new->rb_hole_size,
  565. &mm->holes_size);
  566. rb_replace_node(&old->rb_hole_addr,
  567. &new->rb_hole_addr,
  568. &mm->holes_addr);
  569. }
  570. clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &old->flags);
  571. }
  572. EXPORT_SYMBOL(drm_mm_replace_node);
  573. /**
  574. * DOC: lru scan roster
  575. *
  576. * Very often GPUs need to have continuous allocations for a given object. When
  577. * evicting objects to make space for a new one it is therefore not most
  578. * efficient when we simply start to select all objects from the tail of an LRU
  579. * until there's a suitable hole: Especially for big objects or nodes that
  580. * otherwise have special allocation constraints there's a good chance we evict
  581. * lots of (smaller) objects unnecessarily.
  582. *
  583. * The DRM range allocator supports this use-case through the scanning
  584. * interfaces. First a scan operation needs to be initialized with
  585. * drm_mm_scan_init() or drm_mm_scan_init_with_range(). The driver adds
  586. * objects to the roster, probably by walking an LRU list, but this can be
  587. * freely implemented. Eviction candidates are added using
  588. * drm_mm_scan_add_block() until a suitable hole is found or there are no
  589. * further evictable objects. Eviction roster metadata is tracked in &struct
  590. * drm_mm_scan.
  591. *
  592. * The driver must walk through all objects again in exactly the reverse
  593. * order to restore the allocator state. Note that while the allocator is used
  594. * in the scan mode no other operation is allowed.
  595. *
  596. * Finally the driver evicts all objects selected (drm_mm_scan_remove_block()
  597. * reported true) in the scan, and any overlapping nodes after color adjustment
  598. * (drm_mm_scan_color_evict()). Adding and removing an object is O(1), and
  599. * since freeing a node is also O(1) the overall complexity is
  600. * O(scanned_objects). So like the free stack which needs to be walked before a
  601. * scan operation even begins this is linear in the number of objects. It
  602. * doesn't seem to hurt too badly.
  603. */
  604. /**
  605. * drm_mm_scan_init_with_range - initialize range-restricted lru scanning
  606. * @scan: scan state
  607. * @mm: drm_mm to scan
  608. * @size: size of the allocation
  609. * @alignment: alignment of the allocation
  610. * @color: opaque tag value to use for the allocation
  611. * @start: start of the allowed range for the allocation
  612. * @end: end of the allowed range for the allocation
  613. * @mode: fine-tune the allocation search and placement
  614. *
  615. * This simply sets up the scanning routines with the parameters for the desired
  616. * hole.
  617. *
  618. * Warning:
  619. * As long as the scan list is non-empty, no other operations than
  620. * adding/removing nodes to/from the scan list are allowed.
  621. */
  622. void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
  623. struct drm_mm *mm,
  624. u64 size,
  625. u64 alignment,
  626. unsigned long color,
  627. u64 start,
  628. u64 end,
  629. enum drm_mm_insert_mode mode)
  630. {
  631. DRM_MM_BUG_ON(start >= end);
  632. DRM_MM_BUG_ON(!size || size > end - start);
  633. DRM_MM_BUG_ON(mm->scan_active);
  634. scan->mm = mm;
  635. if (alignment <= 1)
  636. alignment = 0;
  637. scan->color = color;
  638. scan->alignment = alignment;
  639. scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0;
  640. scan->size = size;
  641. scan->mode = mode;
  642. DRM_MM_BUG_ON(end <= start);
  643. scan->range_start = start;
  644. scan->range_end = end;
  645. scan->hit_start = U64_MAX;
  646. scan->hit_end = 0;
  647. }
  648. EXPORT_SYMBOL(drm_mm_scan_init_with_range);
  649. /**
  650. * drm_mm_scan_add_block - add a node to the scan list
  651. * @scan: the active drm_mm scanner
  652. * @node: drm_mm_node to add
  653. *
  654. * Add a node to the scan list that might be freed to make space for the desired
  655. * hole.
  656. *
  657. * Returns:
  658. * True if a hole has been found, false otherwise.
  659. */
  660. bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
  661. struct drm_mm_node *node)
  662. {
  663. struct drm_mm *mm = scan->mm;
  664. struct drm_mm_node *hole;
  665. u64 hole_start, hole_end;
  666. u64 col_start, col_end;
  667. u64 adj_start, adj_end;
  668. DRM_MM_BUG_ON(node->mm != mm);
  669. DRM_MM_BUG_ON(!drm_mm_node_allocated(node));
  670. DRM_MM_BUG_ON(drm_mm_node_scanned_block(node));
  671. __set_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
  672. mm->scan_active++;
  673. /* Remove this block from the node_list so that we enlarge the hole
  674. * (distance between the end of our previous node and the start of
  675. * or next), without poisoning the link so that we can restore it
  676. * later in drm_mm_scan_remove_block().
  677. */
  678. hole = list_prev_entry(node, node_list);
  679. DRM_MM_BUG_ON(list_next_entry(hole, node_list) != node);
  680. __list_del_entry(&node->node_list);
  681. hole_start = __drm_mm_hole_node_start(hole);
  682. hole_end = __drm_mm_hole_node_end(hole);
  683. col_start = hole_start;
  684. col_end = hole_end;
  685. if (mm->color_adjust)
  686. mm->color_adjust(hole, scan->color, &col_start, &col_end);
  687. adj_start = max(col_start, scan->range_start);
  688. adj_end = min(col_end, scan->range_end);
  689. if (adj_end <= adj_start || adj_end - adj_start < scan->size)
  690. return false;
  691. if (scan->mode == DRM_MM_INSERT_HIGH)
  692. adj_start = adj_end - scan->size;
  693. if (scan->alignment) {
  694. u64 rem;
  695. if (likely(scan->remainder_mask))
  696. rem = adj_start & scan->remainder_mask;
  697. else
  698. div64_u64_rem(adj_start, scan->alignment, &rem);
  699. if (rem) {
  700. adj_start -= rem;
  701. if (scan->mode != DRM_MM_INSERT_HIGH)
  702. adj_start += scan->alignment;
  703. if (adj_start < max(col_start, scan->range_start) ||
  704. min(col_end, scan->range_end) - adj_start < scan->size)
  705. return false;
  706. if (adj_end <= adj_start ||
  707. adj_end - adj_start < scan->size)
  708. return false;
  709. }
  710. }
  711. scan->hit_start = adj_start;
  712. scan->hit_end = adj_start + scan->size;
  713. DRM_MM_BUG_ON(scan->hit_start >= scan->hit_end);
  714. DRM_MM_BUG_ON(scan->hit_start < hole_start);
  715. DRM_MM_BUG_ON(scan->hit_end > hole_end);
  716. return true;
  717. }
  718. EXPORT_SYMBOL(drm_mm_scan_add_block);
  719. /**
  720. * drm_mm_scan_remove_block - remove a node from the scan list
  721. * @scan: the active drm_mm scanner
  722. * @node: drm_mm_node to remove
  723. *
  724. * Nodes **must** be removed in exactly the reverse order from the scan list as
  725. * they have been added (e.g. using list_add() as they are added and then
  726. * list_for_each() over that eviction list to remove), otherwise the internal
  727. * state of the memory manager will be corrupted.
  728. *
  729. * When the scan list is empty, the selected memory nodes can be freed. An
  730. * immediately following drm_mm_insert_node_in_range_generic() or one of the
  731. * simpler versions of that function with !DRM_MM_SEARCH_BEST will then return
  732. * the just freed block (because it's at the top of the free_stack list).
  733. *
  734. * Returns:
  735. * True if this block should be evicted, false otherwise. Will always
  736. * return false when no hole has been found.
  737. */
  738. bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
  739. struct drm_mm_node *node)
  740. {
  741. struct drm_mm_node *prev_node;
  742. DRM_MM_BUG_ON(node->mm != scan->mm);
  743. DRM_MM_BUG_ON(!drm_mm_node_scanned_block(node));
  744. __clear_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags);
  745. DRM_MM_BUG_ON(!node->mm->scan_active);
  746. node->mm->scan_active--;
  747. /* During drm_mm_scan_add_block() we decoupled this node leaving
  748. * its pointers intact. Now that the caller is walking back along
  749. * the eviction list we can restore this block into its rightful
  750. * place on the full node_list. To confirm that the caller is walking
  751. * backwards correctly we check that prev_node->next == node->next,
  752. * i.e. both believe the same node should be on the other side of the
  753. * hole.
  754. */
  755. prev_node = list_prev_entry(node, node_list);
  756. DRM_MM_BUG_ON(list_next_entry(prev_node, node_list) !=
  757. list_next_entry(node, node_list));
  758. list_add(&node->node_list, &prev_node->node_list);
  759. return (node->start + node->size > scan->hit_start &&
  760. node->start < scan->hit_end);
  761. }
  762. EXPORT_SYMBOL(drm_mm_scan_remove_block);
  763. /**
  764. * drm_mm_scan_color_evict - evict overlapping nodes on either side of hole
  765. * @scan: drm_mm scan with target hole
  766. *
  767. * After completing an eviction scan and removing the selected nodes, we may
  768. * need to remove a few more nodes from either side of the target hole if
  769. * mm.color_adjust is being used.
  770. *
  771. * Returns:
  772. * A node to evict, or NULL if there are no overlapping nodes.
  773. */
  774. struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan)
  775. {
  776. struct drm_mm *mm = scan->mm;
  777. struct drm_mm_node *hole;
  778. u64 hole_start, hole_end;
  779. DRM_MM_BUG_ON(list_empty(&mm->hole_stack));
  780. if (!mm->color_adjust)
  781. return NULL;
  782. /*
  783. * The hole found during scanning should ideally be the first element
  784. * in the hole_stack list, but due to side-effects in the driver it
  785. * may not be.
  786. */
  787. list_for_each_entry(hole, &mm->hole_stack, hole_stack) {
  788. hole_start = __drm_mm_hole_node_start(hole);
  789. hole_end = hole_start + hole->hole_size;
  790. if (hole_start <= scan->hit_start &&
  791. hole_end >= scan->hit_end)
  792. break;
  793. }
  794. /* We should only be called after we found the hole previously */
  795. DRM_MM_BUG_ON(&hole->hole_stack == &mm->hole_stack);
  796. if (unlikely(&hole->hole_stack == &mm->hole_stack))
  797. return NULL;
  798. DRM_MM_BUG_ON(hole_start > scan->hit_start);
  799. DRM_MM_BUG_ON(hole_end < scan->hit_end);
  800. mm->color_adjust(hole, scan->color, &hole_start, &hole_end);
  801. if (hole_start > scan->hit_start)
  802. return hole;
  803. if (hole_end < scan->hit_end)
  804. return list_next_entry(hole, node_list);
  805. return NULL;
  806. }
  807. EXPORT_SYMBOL(drm_mm_scan_color_evict);
  808. /**
  809. * drm_mm_init - initialize a drm-mm allocator
  810. * @mm: the drm_mm structure to initialize
  811. * @start: start of the range managed by @mm
  812. * @size: end of the range managed by @mm
  813. *
  814. * Note that @mm must be cleared to 0 before calling this function.
  815. */
  816. void drm_mm_init(struct drm_mm *mm, u64 start, u64 size)
  817. {
  818. DRM_MM_BUG_ON(start + size <= start);
  819. mm->color_adjust = NULL;
  820. INIT_LIST_HEAD(&mm->hole_stack);
  821. mm->interval_tree = RB_ROOT_CACHED;
  822. mm->holes_size = RB_ROOT_CACHED;
  823. mm->holes_addr = RB_ROOT;
  824. /* Clever trick to avoid a special case in the free hole tracking. */
  825. INIT_LIST_HEAD(&mm->head_node.node_list);
  826. mm->head_node.flags = 0;
  827. mm->head_node.mm = mm;
  828. mm->head_node.start = start + size;
  829. mm->head_node.size = -size;
  830. add_hole(&mm->head_node);
  831. mm->scan_active = 0;
  832. #ifdef CONFIG_DRM_DEBUG_MM
  833. stack_depot_init();
  834. #endif
  835. }
  836. EXPORT_SYMBOL(drm_mm_init);
  837. /**
  838. * drm_mm_takedown - clean up a drm_mm allocator
  839. * @mm: drm_mm allocator to clean up
  840. *
  841. * Note that it is a bug to call this function on an allocator which is not
  842. * clean.
  843. */
  844. void drm_mm_takedown(struct drm_mm *mm)
  845. {
  846. if (WARN(!drm_mm_clean(mm),
  847. "Memory manager not clean during takedown.\n"))
  848. show_leaks(mm);
  849. }
  850. EXPORT_SYMBOL(drm_mm_takedown);
  851. static u64 drm_mm_dump_hole(struct drm_printer *p, const struct drm_mm_node *entry)
  852. {
  853. u64 start, size;
  854. size = entry->hole_size;
  855. if (size) {
  856. start = drm_mm_hole_node_start(entry);
  857. drm_printf(p, "%#018llx-%#018llx: %llu: free\n",
  858. start, start + size, size);
  859. }
  860. return size;
  861. }
  862. /**
  863. * drm_mm_print - print allocator state
  864. * @mm: drm_mm allocator to print
  865. * @p: DRM printer to use
  866. */
  867. void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p)
  868. {
  869. const struct drm_mm_node *entry;
  870. u64 total_used = 0, total_free = 0, total = 0;
  871. total_free += drm_mm_dump_hole(p, &mm->head_node);
  872. drm_mm_for_each_node(entry, mm) {
  873. drm_printf(p, "%#018llx-%#018llx: %llu: used\n", entry->start,
  874. entry->start + entry->size, entry->size);
  875. total_used += entry->size;
  876. total_free += drm_mm_dump_hole(p, entry);
  877. }
  878. total = total_free + total_used;
  879. drm_printf(p, "total: %llu, used %llu free %llu\n", total,
  880. total_used, total_free);
  881. }
  882. EXPORT_SYMBOL(drm_mm_print);