Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206// SPDX-License-Identifier: MIT/* * Copyright © 2021 Intel Corporation */
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
#include <linux/bug.h>#include <linux/export.h>#include <linux/kmemleak.h>#include <linux/module.h>#include <linux/sizes.h>#include <linux/slab.h>
#include <linux/gpu_buddy.h>
/** * gpu_buddy_assert - assert a condition in the buddy allocator * @condition: condition expected to be true * * When CONFIG_KUNIT is enabled, evaluates @condition and, if false, triggers * a WARN_ON() and also calls kunit_fail_current_test() so that any running * kunit test is properly marked as failed. The stringified condition is * included in the failure message for easy identification. * * When CONFIG_KUNIT is not enabled, this reduces to WARN_ON() so production * builds retain the same warning semantics as before. */#if IS_ENABLED(CONFIG_KUNIT)#include <kunit/test-bug.h>#define gpu_buddy_assert(condition) do { \ if (WARN_ON(!(condition))) \ kunit_fail_current_test("gpu_buddy_assert(" #condition ")"); \} while (0)#else#define gpu_buddy_assert(condition) WARN_ON(!(condition))#endif
static struct kmem_cache *slab_blocks;static struct kmem_cache *slab_extents;
/* * Dirty tracker * ------------- * * The dirty tracker maintains an augmented interval rbtree of contiguous * dirty address ranges, decoupled from the buddy free trees. * Each node covers a maximal coalesced run; adjacent extents are merged * on insertion so the tree always holds the smallest possible number of * extents. The augmentation field @subtree_max_size lets the allocator * locate the largest dirty extent in O(log E). * * Free trees (mm->free_tree[]) * ---------------------------- * * Per-order augmented rbtrees of FREE buddy blocks, keyed by offset. * Every node carries: * - subtree_max_alignment: largest natural alignment in the subtree, * used by aligned/range allocations to skip unsuitable subtrees in * O(log N). * - subtree_block_state: the highest clear class (DIRTY < MIXED < CLEAR) * of any block in the subtree, maintained as a max augment. A value of * >= MIXED means a clear-or-mixed block exists; == CLEAR means a * fully-clear block exists. * * Block classes * ------------- * * Each FREE block falls into one of three classes, determined in * mark_free() by querying the dirty tracker for the block's range: * * clear -- HEADER_CLEAR set; no dirty extent overlaps the range. * mixed -- HEADER_CLEAR unset; range has both dirty and clear bytes. * dirty -- HEADER_CLEAR unset; range is fully dirty. * * Clear allocation * ---------------- * * A clear (CLEAR_ALLOCATION) request prefers clear -> mixed -> dirty. * Climbing from the requested order up to max_order, rbtree_last_clear_free_block() * returns, in one O(log N) descent per order, the right-most clear-or-mixed block * (fully-clear preferred over mixed) at the lowest order whose free tree contains * such a block. Only if no clear-or-mixed block exists at any order >= the * requested one does it fall back to a dirty block. * * Clear state is reported to the driver per whole block via HEADER_CLEAR, so a * fully-clear block of the requested order lets the driver skip the clear pass. * * The effective allocation preference depends on how the driver handles * freed blocks: * * 1) Never clear on free: * No free block contains clear bytes, so clear allocations always * fall back to dirty blocks. * * 2) Always clear on free: * Freed blocks become clear while untouched blocks remain dirty. * Merging clear and dirty buddies produces mixed blocks, which are * reclassified when split. Over time, clear blocks become dominant, * so clear allocations are typically satisfied from clear blocks, * following a clear -> mixed -> dirty preference. * * 3) Selective clear on free: * For each order examined, fully-clear blocks are preferred over * mixed blocks, and mixed blocks are preferred over dirty blocks. * If a clear or mixed block is found at an order, it is selected * without searching higher orders. Dirty blocks are used only when * no clear or mixed block exists at any eligible order. */
static u64 extent_size(struct gpu_dirty_extent *dirty_extent){ return dirty_extent->end - dirty_extent->start;}
RB_DECLARE_CALLBACKS_MAX(static, gpu_dirty_augment_cb, struct gpu_dirty_extent, rb, u64, subtree_max_size, extent_size)
static struct gpu_dirty_extent *extent_alloc(struct gpu_dirty_tracker *dirty_tracker){ return kmem_cache_alloc(slab_extents, GFP_KERNEL);}
static void extent_free(struct gpu_dirty_tracker *dirty_tracker, struct gpu_dirty_extent *dirty_extent){ kmem_cache_free(slab_extents, dirty_extent);}
/* Return the rightmost extent whose start is strictly below @offset. */static struct gpu_dirty_extent *prev_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset){ struct rb_node *rb = dirty_tracker->root.rb_node; struct gpu_dirty_extent *dirty_extent = NULL;
while (rb) { struct gpu_dirty_extent *tmp_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
if (tmp_extent->start < offset) { dirty_extent = tmp_extent; rb = rb->rb_right; } else { rb = rb->rb_left; } }
return dirty_extent;}
/* Return the leftmost extent whose start is at or above @offset. */static struct gpu_dirty_extent *next_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset){ struct rb_node *rb = dirty_tracker->root.rb_node; struct gpu_dirty_extent *dirty_extent = NULL;
while (rb) { struct gpu_dirty_extent *tmp_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
if (tmp_extent->start >= offset) { dirty_extent = tmp_extent; rb = rb->rb_left; } else { rb = rb->rb_right; } }
return dirty_extent;}
static void insert_extent(struct gpu_dirty_tracker *dirty_tracker, struct gpu_dirty_extent *dirty_extent){ struct rb_node **link = &dirty_tracker->root.rb_node; struct rb_node *parent = NULL; u64 size = extent_size(dirty_extent);
while (*link) { struct gpu_dirty_extent *tmp_extent;
parent = *link; tmp_extent = rb_entry(parent, struct gpu_dirty_extent, rb);
if (tmp_extent->subtree_max_size < size) tmp_extent->subtree_max_size = size;
if (dirty_extent->start < tmp_extent->start) link = &parent->rb_left; else link = &parent->rb_right; }
dirty_extent->subtree_max_size = size; rb_link_node(&dirty_extent->rb, parent, link); rb_insert_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb);}
static void remove_extent(struct gpu_dirty_tracker *dirty_tracker, struct gpu_dirty_extent *dirty_extent){ rb_erase_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb); RB_CLEAR_NODE(&dirty_extent->rb);}
static void gpu_dirty_tracker_init(struct gpu_dirty_tracker *dirty_tracker){ dirty_tracker->root = RB_ROOT; dirty_tracker->total_dirty = 0;}
static void gpu_dirty_tracker_empty(struct gpu_dirty_tracker *dirty_tracker){ struct rb_node *rb;
while ((rb = rb_first(&dirty_tracker->root))) { struct gpu_dirty_extent *dirty_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
remove_extent(dirty_tracker, dirty_extent); extent_free(dirty_tracker, dirty_extent); }
dirty_tracker->total_dirty = 0;}
static void gpu_dirty_tracker_fini(struct gpu_dirty_tracker *dirty_tracker){ gpu_dirty_tracker_empty(dirty_tracker);}
/* * Mark the range [start, start + size] as dirty. Merge with the neighbour on * each side if they are contiguous, so the tree never holds two adjacent ranges. */static void gpu_dirty_tracker_mark_dirty(struct gpu_dirty_tracker *dirty_tracker, u64 start, u64 size){ struct gpu_dirty_extent *left, *right, *dirty_extent; u64 end = start + size;
gpu_buddy_assert(size);
/* Find contiguous neighbours, if any. */ left = prev_extent(dirty_tracker, start); if (left && left->end != start) left = NULL;
right = next_extent(dirty_tracker, end); if (right && right->start != end) right = NULL;
if (left && right) { /* Merge left + new + right into a single extent. */ remove_extent(dirty_tracker, left); remove_extent(dirty_tracker, right); left->end = right->end; extent_free(dirty_tracker, right); insert_extent(dirty_tracker, left); } else if (left) { /* Extend left neighbour rightwards. */ remove_extent(dirty_tracker, left); left->end = end; insert_extent(dirty_tracker, left); } else if (right) { /* Extend right neighbour leftwards. */ remove_extent(dirty_tracker, right); right->start = start; insert_extent(dirty_tracker, right); } else { /* Standalone extent. */ dirty_extent = extent_alloc(dirty_tracker); if (!dirty_extent) { pr_warn_once("dirty extent allocation failed, skipping tracker update\n"); return; } dirty_extent->start = start; dirty_extent->end = end; insert_extent(dirty_tracker, dirty_extent); }
dirty_tracker->total_dirty += size;}
/* * Remove the range [start, start + size] from the dirty tracker. Punch the * range out of every overlapping dirty extent, splitting one extent in two if * the removed range falls strictly inside it. */static void gpu_dirty_tracker_remove_range(struct gpu_dirty_tracker *dirty_tracker, u64 start, u64 size){ struct gpu_dirty_extent *dirty_extent, *next; u64 end = start + size;
gpu_buddy_assert(size);
dirty_extent = prev_extent(dirty_tracker, start + 1); if (!dirty_extent) dirty_extent = next_extent(dirty_tracker, start);
while (dirty_extent && dirty_extent->start < end) { struct rb_node *next_node = rb_next(&dirty_extent->rb); u64 extent_start = dirty_extent->start; u64 extent_end = dirty_extent->end;
if (next_node) next = rb_entry(next_node, struct gpu_dirty_extent, rb); else next = NULL;
/* Skip a non-overlapping neighbour returned by prev_extent(). */ if (extent_end <= start) { dirty_extent = next; continue; }
if (extent_start < start && extent_end > end) { /* * Removed range lies strictly inside this dirty extent: * split it into the dirty left and right halves. */ struct gpu_dirty_extent *right = extent_alloc(dirty_tracker);
if (!right) { pr_warn_once("dirty extent allocation failed, skipping tracker update\n"); dirty_extent = next; continue; }
remove_extent(dirty_tracker, dirty_extent);
dirty_extent->end = start; right->start = end; right->end = extent_end;
insert_extent(dirty_tracker, dirty_extent); insert_extent(dirty_tracker, right);
dirty_tracker->total_dirty -= size; } else if (extent_start >= start && extent_end <= end) { /* Extent fully covered: drop it. */ remove_extent(dirty_tracker, dirty_extent); extent_free(dirty_tracker, dirty_extent);
dirty_tracker->total_dirty -= (extent_end - extent_start); } else if (extent_start < start) { /* Extent overlaps from the left: trim its right end. */ remove_extent(dirty_tracker, dirty_extent); dirty_extent->end = start; insert_extent(dirty_tracker, dirty_extent);
dirty_tracker->total_dirty -= (extent_end - start); } else { /* Extent overlaps from the right: trim its left end. */ remove_extent(dirty_tracker, dirty_extent); dirty_extent->start = end; insert_extent(dirty_tracker, dirty_extent);
dirty_tracker->total_dirty -= (end - extent_start); }
dirty_extent = next; }}
static enum gpu_block_stategpu_dirty_range_state(struct gpu_dirty_tracker *dirty_tracker, u64 start, u64 size){ struct gpu_dirty_extent *dirty_extent; u64 end = start + size;
dirty_extent = prev_extent(dirty_tracker, start + 1); if (dirty_extent) { if (dirty_extent->start <= start && dirty_extent->end >= end) return GPU_BLOCK_DIRTY; if (dirty_extent->start < end && dirty_extent->end > start) return GPU_BLOCK_MIXED; }
dirty_extent = next_extent(dirty_tracker, start); if (dirty_extent && dirty_extent->start < end) return GPU_BLOCK_MIXED;
return GPU_BLOCK_CLEAR;}
static struct rb_node *dirty_tracker_descend_right(struct rb_node *node, u64 min_size){ while (node->rb_right) { struct gpu_dirty_extent *tmp_extent;
tmp_extent = rb_entry(node->rb_right, struct gpu_dirty_extent, rb);
if (tmp_extent->subtree_max_size < min_size) break; node = node->rb_right; }
return node;}
static struct gpu_dirty_extent *gpu_dirty_tracker_find(struct gpu_dirty_tracker *dirty_tracker, u64 min_size, u64 *aligned_start_out){ struct rb_node *rb = dirty_tracker->root.rb_node; struct gpu_dirty_extent *root_extent; struct rb_node *parent;
if (!min_size || !is_power_of_2(min_size)) return NULL;
if (!rb) return NULL;
root_extent = rb_entry(rb, struct gpu_dirty_extent, rb); if (root_extent->subtree_max_size < min_size) return NULL;
rb = dirty_tracker_descend_right(rb, min_size);
while (rb) { struct gpu_dirty_extent *dirty_extent; u64 aligned_start;
dirty_extent = rb_entry(rb, struct gpu_dirty_extent, rb); aligned_start = ALIGN(dirty_extent->start, min_size);
/* Check if a min_size block fits after the alignment skip. */ if (aligned_start <= dirty_extent->end && dirty_extent->end - aligned_start >= min_size) { *aligned_start_out = aligned_start; return dirty_extent; }
if (rb->rb_left) { struct gpu_dirty_extent *tmp_extent;
tmp_extent = rb_entry(rb->rb_left, struct gpu_dirty_extent, rb); if (tmp_extent->subtree_max_size >= min_size) { rb = dirty_tracker_descend_right(rb->rb_left, min_size); continue; } }
/* Walk up until we exit a node via its right child. */ parent = rb_parent(rb); while (parent && parent->rb_right != rb) { rb = parent; parent = rb_parent(rb); } rb = parent; }
return NULL;}
static unsigned intgpu_buddy_block_state(struct gpu_buddy_block *block){ return block->header & GPU_BUDDY_HEADER_STATE;}
static boolgpu_buddy_block_is_allocated(struct gpu_buddy_block *block){ return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED;}
static boolgpu_buddy_block_is_split(struct gpu_buddy_block *block){ return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT;}
static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block){ u64 offset = gpu_buddy_block_offset(block);
if (!offset) /* * __ffs64(0) is undefined; offset 0 is maximally aligned, so return * a value greater than any possible alignment. */ return 64 + 1;
return __ffs64(offset);}
static inline enum gpu_block_stategpu_block_cached_state(struct gpu_buddy_block *block){ if (gpu_buddy_block_is_clear(block)) return GPU_BLOCK_CLEAR; if (block->has_clear) return GPU_BLOCK_MIXED; return GPU_BLOCK_DIRTY;}
static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block){ enum gpu_block_state block_state; struct gpu_buddy_block *right; struct gpu_buddy_block *left; unsigned int max_align;
max_align = gpu_buddy_block_offset_alignment(block); block_state = gpu_block_cached_state(block);
left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb); if (left) { if (left->subtree_max_alignment > max_align) max_align = left->subtree_max_alignment;
block_state = max(block_state, left->subtree_block_state); }
right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block, rb); if (right) { if (right->subtree_max_alignment > max_align) max_align = right->subtree_max_alignment;
block_state = max(block_state, right->subtree_block_state); }
block->subtree_max_alignment = max_align; block->subtree_block_state = block_state;}
static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop){ while (rb != stop) { struct gpu_buddy_block *block; unsigned int old_align; enum gpu_block_state old_block_state;
block = rb_entry(rb, struct gpu_buddy_block, rb); old_align = block->subtree_max_alignment; old_block_state = block->subtree_block_state;
gpu_buddy_augment_compute(block); if (block->subtree_max_alignment == old_align && block->subtree_block_state == old_block_state) break;
rb = rb_parent(&block->rb); }}
static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct rb_node *rb_new){ struct gpu_buddy_block *old; struct gpu_buddy_block *new;
old = rb_entry(rb_old, struct gpu_buddy_block, rb); new = rb_entry(rb_new, struct gpu_buddy_block, rb);
new->subtree_max_alignment = old->subtree_max_alignment; new->subtree_block_state = old->subtree_block_state;}
static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new){ struct gpu_buddy_block *old; struct gpu_buddy_block *new;
old = rb_entry(rb_old, struct gpu_buddy_block, rb); new = rb_entry(rb_new, struct gpu_buddy_block, rb);
new->subtree_max_alignment = old->subtree_max_alignment; new->subtree_block_state = old->subtree_block_state;
gpu_buddy_augment_compute(old);}
static const struct rb_augment_callbacks gpu_buddy_augment_cb = { .propagate = gpu_buddy_augment_propagate, .copy = gpu_buddy_augment_copy, .rotate = gpu_buddy_augment_rotate,};
static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm, struct gpu_buddy_block *parent, unsigned int order, u64 offset){ struct gpu_buddy_block *block;
BUG_ON(order > GPU_BUDDY_MAX_ORDER);
block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); if (!block) return NULL;
block->header = offset; block->header |= order; block->parent = parent;
RB_CLEAR_NODE(&block->rb);
BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED); return block;}
static void gpu_block_free(struct gpu_buddy *mm, struct gpu_buddy_block *block){ kmem_cache_free(slab_blocks, block);}
static struct gpu_buddy_block *rbtree_get_free_block(const struct rb_node *node){ return node ? rb_entry(node, struct gpu_buddy_block, rb) : NULL;}
static struct gpu_buddy_block *rbtree_last_free_block(struct rb_root *root){ return rbtree_get_free_block(rb_last(root));}
static struct gpu_buddy_block *rbtree_last_clear_free_block(struct rb_root *root, enum gpu_block_state min_block_state){ struct rb_node *node = root->rb_node; struct gpu_buddy_block *block = NULL; struct gpu_buddy_block *root_block; enum gpu_block_state target_state;
root_block = rbtree_get_free_block(node); if (!root_block || root_block->subtree_block_state < min_block_state) return NULL;
target_state = root_block->subtree_block_state;
while (node) { struct gpu_buddy_block *right_block; struct gpu_buddy_block *node_block;
node_block = rbtree_get_free_block(node); right_block = rbtree_get_free_block(node->rb_right);
if (right_block && right_block->subtree_block_state >= target_state) { node = node->rb_right; continue; }
if (gpu_block_cached_state(node_block) == target_state) { block = node_block; break; }
node = node->rb_left; }
return block;}
static void rbtree_insert(struct gpu_buddy *mm, struct gpu_buddy_block *block){ struct rb_node **link, *parent = NULL; enum gpu_block_state block_state; struct gpu_buddy_block *node; unsigned int block_alignment; struct rb_root *root; unsigned int order;
order = gpu_buddy_block_order(block); block_alignment = gpu_buddy_block_offset_alignment(block); block_state = gpu_block_cached_state(block);
root = &mm->free_tree[order]; link = &root->rb_node;
while (*link) { parent = *link; node = rbtree_get_free_block(parent); /* * Manual augmentation update during insertion traversal. Required * because rb_insert_augmented() only calls rotate callback during * rotations. This ensures all ancestors on the insertion path have * correct subtree_max_alignment / subtree_block_state values. */ if (node->subtree_max_alignment < block_alignment) node->subtree_max_alignment = block_alignment; if (node->subtree_block_state < block_state) node->subtree_block_state = block_state;
if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node)) link = &parent->rb_left; else link = &parent->rb_right; }
block->subtree_max_alignment = block_alignment; block->subtree_block_state = block_state; rb_link_node(&block->rb, parent, link); rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);}
static void rbtree_remove(struct gpu_buddy *mm, struct gpu_buddy_block *block){ unsigned int order = gpu_buddy_block_order(block);
rb_erase_augmented(&block->rb, &mm->free_tree[order], &gpu_buddy_augment_cb); RB_CLEAR_NODE(&block->rb);}
static void mark_allocated(struct gpu_buddy *mm, struct gpu_buddy_block *block){ block->header &= ~GPU_BUDDY_HEADER_STATE; block->header |= GPU_BUDDY_ALLOCATED;
block->has_clear = false;
mm->free_scoreboard[gpu_buddy_block_order(block)]--; mm->used_scoreboard[gpu_buddy_block_order(block)]++;
rbtree_remove(mm, block);}
static void __mark_free(struct gpu_buddy *mm, struct gpu_buddy_block *block, enum gpu_block_state block_state){ if (gpu_buddy_block_is_allocated(block)) mm->used_scoreboard[gpu_buddy_block_order(block)]--;
block->header &= ~GPU_BUDDY_HEADER_STATE; block->header |= GPU_BUDDY_FREE;
block->header &= ~GPU_BUDDY_HEADER_CLEAR;
block->has_clear = (block_state != GPU_BLOCK_DIRTY); if (block_state == GPU_BLOCK_CLEAR) block->header |= GPU_BUDDY_HEADER_CLEAR;
mm->free_scoreboard[gpu_buddy_block_order(block)]++;
rbtree_insert(mm, block);}
static void mark_free(struct gpu_buddy *mm, struct gpu_buddy_block *block){ enum gpu_block_state block_state;
block_state = gpu_dirty_range_state(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block)); __mark_free(mm, block, block_state);}
static void mark_split(struct gpu_buddy *mm, struct gpu_buddy_block *block){ block->header &= ~GPU_BUDDY_HEADER_STATE; block->header |= GPU_BUDDY_SPLIT;
mm->free_scoreboard[gpu_buddy_block_order(block)]--;
rbtree_remove(mm, block);}
static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2){ return s1 <= e2 && e1 >= s2;}
static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2){ return s1 <= s2 && e1 >= e2;}
static struct gpu_buddy_block *__get_buddy(struct gpu_buddy_block *block){ struct gpu_buddy_block *parent;
parent = block->parent; if (!parent) return NULL;
if (parent->left == block) return parent->right;
return parent->left;}
static unsigned int __gpu_buddy_free(struct gpu_buddy *mm, struct gpu_buddy_block *block){ enum gpu_block_state block_state; struct gpu_buddy_block *parent; unsigned int order;
block_state = gpu_block_cached_state(block);
while ((parent = block->parent)) { struct gpu_buddy_block *buddy = __get_buddy(block);
if (!gpu_buddy_block_is_free(buddy)) break;
if (block_state != GPU_BLOCK_MIXED) { enum gpu_block_state buddy_state;
buddy_state = gpu_block_cached_state(buddy);
if (buddy_state != block_state) block_state = GPU_BLOCK_MIXED; }
rbtree_remove(mm, buddy); mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;
if (gpu_buddy_block_is_allocated(block)) mm->used_scoreboard[gpu_buddy_block_order(block)]--;
gpu_block_free(mm, block); gpu_block_free(mm, buddy);
block = parent; }
order = gpu_buddy_block_order(block); __mark_free(mm, block, block_state);
return order;}
/** * gpu_buddy_init - init memory manager * * @mm: GPU buddy manager to initialize * @size: size in bytes to manage * @chunk_size: minimum page size in bytes for our allocations * * Initializes the memory manager and its resources. * * Returns: * 0 on success, error code on failure. */int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size){ unsigned int root_count = 0; u64 offset = 0;
if (size < chunk_size) return -EINVAL;
if (chunk_size < SZ_4K) return -EINVAL;
if (!is_power_of_2(chunk_size)) return -EINVAL;
size = round_down(size, chunk_size);
mm->size = size; mm->avail = size; mm->chunk_size = chunk_size; mm->max_order = ilog2(size) - ilog2(chunk_size);
BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER);
mm->free_scoreboard = kcalloc(mm->max_order + 1, sizeof(*mm->free_scoreboard), GFP_KERNEL); if (!mm->free_scoreboard) return -ENOMEM;
mm->used_scoreboard = kcalloc(mm->max_order + 1, sizeof(*mm->used_scoreboard), GFP_KERNEL); if (!mm->used_scoreboard) goto out_free_free_scoreboard;
mm->free_tree = kcalloc(mm->max_order + 1, sizeof(struct rb_root), GFP_KERNEL); if (!mm->free_tree) goto out_free_used_scoreboard;
gpu_dirty_tracker_init(&mm->dirty);
mm->n_roots = hweight64(size);
mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots); if (!mm->roots) goto out_free_tree;
/* * Split into power-of-two blocks, in case we are given a size that is * not itself a power-of-two. */ do { struct gpu_buddy_block *root; unsigned int order; u64 root_size;
order = ilog2(size) - ilog2(chunk_size); root_size = chunk_size << order;
root = gpu_block_alloc(mm, NULL, order, offset); if (!root) goto out_free_roots;
gpu_dirty_tracker_mark_dirty(&mm->dirty, offset, root_size); __mark_free(mm, root, GPU_BLOCK_DIRTY);
BUG_ON(root_count > mm->max_order); BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size);
mm->roots[root_count] = root;
offset += root_size; size -= root_size; root_count++; } while (size);
#ifdef CONFIG_LOCKDEP mm->lock_dep_map = NULL;#endif return 0;
out_free_roots: while (root_count--) gpu_block_free(mm, mm->roots[root_count]); kfree(mm->roots);out_free_tree: gpu_dirty_tracker_fini(&mm->dirty); kfree(mm->free_tree);out_free_used_scoreboard: kfree(mm->used_scoreboard);out_free_free_scoreboard: kfree(mm->free_scoreboard); return -ENOMEM;}EXPORT_SYMBOL(gpu_buddy_init);
/** * gpu_buddy_fini - tear down the memory manager * * @mm: GPU buddy manager to free * * Cleanup memory manager resources and the freetree */void gpu_buddy_fini(struct gpu_buddy *mm){ u64 root_size, size; unsigned int order; int i;
size = mm->size;
for (i = 0; i < mm->n_roots; ++i) { order = ilog2(size) - ilog2(mm->chunk_size); root_size = mm->chunk_size << order;
gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i])); gpu_block_free(mm, mm->roots[i]); size -= root_size; }
gpu_buddy_assert(mm->avail == mm->size);
for (i = 0; i <= mm->max_order; ++i) gpu_buddy_assert(!mm->used_scoreboard[i]);
gpu_dirty_tracker_fini(&mm->dirty); kfree(mm->free_tree); kfree(mm->roots); kfree(mm->free_scoreboard); kfree(mm->used_scoreboard);}EXPORT_SYMBOL(gpu_buddy_fini);
static int split_block(struct gpu_buddy *mm, struct gpu_buddy_block *block){ unsigned int block_order = gpu_buddy_block_order(block) - 1; u64 offset = gpu_buddy_block_offset(block); enum gpu_block_state parent_state;
BUG_ON(!gpu_buddy_block_is_free(block)); BUG_ON(!gpu_buddy_block_order(block));
block->left = gpu_block_alloc(mm, block, block_order, offset); if (!block->left) return -ENOMEM;
block->right = gpu_block_alloc(mm, block, block_order, offset + (mm->chunk_size << block_order)); if (!block->right) { gpu_block_free(mm, block->left); return -ENOMEM; }
parent_state = gpu_block_cached_state(block);
mark_split(mm, block);
if (parent_state == GPU_BLOCK_MIXED) { mark_free(mm, block->left); mark_free(mm, block->right); } else { __mark_free(mm, block->left, parent_state); __mark_free(mm, block->right, parent_state); }
return 0;}
/** * gpu_buddy_reset_clear - reset blocks clear state * * @mm: GPU buddy manager * @is_clear: blocks clear state * * Reset the clear state based on @is_clear value for each block * in the freetree. */void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear){ unsigned int i;
gpu_buddy_driver_lock_held(mm);
gpu_dirty_tracker_empty(&mm->dirty);
for (i = 0; i <= mm->max_order; ++i) { struct gpu_buddy_block *block, *tmp;
rbtree_postorder_for_each_entry_safe(block, tmp, &mm->free_tree[i], rb) { if (is_clear) { if (!gpu_buddy_block_is_clear(block)) block->header |= GPU_BUDDY_HEADER_CLEAR; block->has_clear = true; } else { block->header &= ~GPU_BUDDY_HEADER_CLEAR; block->has_clear = false; gpu_dirty_tracker_mark_dirty(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block)); }
gpu_buddy_augment_compute(block); } }}EXPORT_SYMBOL(gpu_buddy_reset_clear);
static void __gpu_buddy_free_block_internal(struct gpu_buddy *mm, struct gpu_buddy_block *block){ u64 size = gpu_buddy_block_size(mm, block);
gpu_buddy_driver_lock_held(mm); BUG_ON(!gpu_buddy_block_is_allocated(block));
mm->avail += size; __gpu_buddy_free(mm, block);}
/** * gpu_buddy_free_block - free a block * * @mm: GPU buddy manager * @block: block to be freed */void gpu_buddy_free_block(struct gpu_buddy *mm, struct gpu_buddy_block *block){ if (!gpu_buddy_block_is_clear(block)) gpu_dirty_tracker_mark_dirty(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block));
__gpu_buddy_free_block_internal(mm, block);}EXPORT_SYMBOL(gpu_buddy_free_block);
/** * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block * * @mm: GPU buddy manager * @addr: Relative address * * Returns: * gpu_buddy_block on success, NULL or error code on failure */struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr){ struct gpu_buddy_block *block; LIST_HEAD(dfs); u64 end; int i;
gpu_buddy_driver_lock_held(mm);
end = addr + mm->chunk_size - 1; for (i = 0; i < mm->n_roots; ++i) list_add_tail(&mm->roots[i]->tmp_link, &dfs);
do { u64 block_start; u64 block_end;
block = list_first_entry_or_null(&dfs, struct gpu_buddy_block, tmp_link); if (!block) break;
list_del(&block->tmp_link);
block_start = gpu_buddy_block_offset(block); block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
if (!overlaps(addr, end, block_start, block_end)) continue;
if (gpu_buddy_block_is_allocated(block)) return block; else if (gpu_buddy_block_is_free(block)) return NULL;
list_add(&block->right->tmp_link, &dfs); list_add(&block->left->tmp_link, &dfs); } while (1);
return ERR_PTR(-ENXIO);}EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block);
static void __gpu_buddy_free_list(struct gpu_buddy *mm, struct list_head *objects, bool mark_clear, bool mark_dirty){ struct gpu_buddy_block *block, *on; u64 dirty_start = 0, dirty_size = 0;
gpu_buddy_assert(!(mark_dirty && mark_clear));
list_for_each_entry_safe(block, on, objects, link) { u64 offset = gpu_buddy_block_offset(block); u64 size = gpu_buddy_block_size(mm, block);
if (mark_clear) block->header |= GPU_BUDDY_HEADER_CLEAR; else if (mark_dirty) block->header &= ~GPU_BUDDY_HEADER_CLEAR;
/* * Coalesce contiguous dirty blocks into one extent update so * a multi-block contiguous free costs a single mark_dirty(). * Flush the pending extent and start over on a gap. */ if (!gpu_buddy_block_is_clear(block)) { if (dirty_size && (dirty_start + dirty_size == offset || offset + size == dirty_start)) { dirty_start = min(dirty_start, offset); dirty_size += size; } else { if (dirty_size) gpu_dirty_tracker_mark_dirty(&mm->dirty, dirty_start, dirty_size); dirty_start = offset; dirty_size = size; } }
__gpu_buddy_free_block_internal(mm, block); cond_resched(); }
if (dirty_size) gpu_dirty_tracker_mark_dirty(&mm->dirty, dirty_start, dirty_size);
INIT_LIST_HEAD(objects);}
static void gpu_buddy_free_list_internal(struct gpu_buddy *mm, struct list_head *objects){ /* * Don't touch the clear/dirty bit, since allocation is still internal * at this point. For example we might have just failed part of the * allocation. */ __gpu_buddy_free_list(mm, objects, false, false);}
/** * gpu_buddy_free_list - free blocks * * @mm: GPU buddy manager * @objects: input list head to free blocks * @flags: optional flags like GPU_BUDDY_CLEARED */void gpu_buddy_free_list(struct gpu_buddy *mm, struct list_head *objects, unsigned int flags){ bool mark_clear = flags & GPU_BUDDY_CLEARED;
gpu_buddy_driver_lock_held(mm); __gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear);}EXPORT_SYMBOL(gpu_buddy_free_list);
static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, struct gpu_buddy_block *block){ struct gpu_buddy_block *buddy = __get_buddy(block);
if (buddy && (gpu_buddy_block_is_free(block) && gpu_buddy_block_is_free(buddy))) { rbtree_remove(mm, block); mm->free_scoreboard[gpu_buddy_block_order(block)]--; __gpu_buddy_free(mm, block); }}
static struct gpu_buddy_block *__alloc_range_bias(struct gpu_buddy *mm, u64 start, u64 end, unsigned int order, unsigned long flags){ u64 req_size = mm->chunk_size << order; struct gpu_buddy_block *block; LIST_HEAD(dfs); int err; int i;
end = end - 1;
/* * This range-constrained search hands back the highest/right-most * address that satisfies the request: the roots are seeded high-to-low * and the right (higher-address) child is descended first, making * top-down the default placement here. A non-top-down clear request is * the only exception, where the descent is biased towards clear or * clear-containing subtrees to satisfy the clear preference. */ for (i = mm->n_roots - 1; i >= 0; --i) list_add_tail(&mm->roots[i]->tmp_link, &dfs);
do { u64 block_start; u64 block_end;
block = list_first_entry_or_null(&dfs, struct gpu_buddy_block, tmp_link); if (!block) break;
list_del(&block->tmp_link);
if (gpu_buddy_block_order(block) < order) continue;
block_start = gpu_buddy_block_offset(block); block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
if (!overlaps(start, end, block_start, block_end)) continue;
if (gpu_buddy_block_is_allocated(block)) continue;
if (block_start < start || block_end > end) { u64 adjusted_start = max(block_start, start); u64 adjusted_end = min(block_end, end);
if (round_down(adjusted_end + 1, req_size) <= round_up(adjusted_start, req_size)) continue; }
if (contains(start, end, block_start, block_end) && order == gpu_buddy_block_order(block)) { /* * Find the free block within the range. */ if (gpu_buddy_block_is_free(block)) return block;
continue; }
if (!gpu_buddy_block_is_split(block)) { err = split_block(mm, block); if (unlikely(err)) goto err_undo; }
/* * Top-down is a strict address-placement policy, so when it is * requested we ignore clear steering and simply descend the * right (higher-address) child first. Only a non-top-down clear * request biases the descent towards clear/has_clear subtrees. */ if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) && !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) { struct gpu_buddy_block *prefer;
if (gpu_buddy_block_is_clear(block->right)) prefer = block->right; else if (gpu_buddy_block_is_clear(block->left)) prefer = block->left; else if (block->right->has_clear) prefer = block->right; else if (block->left->has_clear) prefer = block->left; else prefer = block->right;
if (prefer == block->right) { list_add(&block->left->tmp_link, &dfs); list_add(&block->right->tmp_link, &dfs); } else { list_add(&block->right->tmp_link, &dfs); list_add(&block->left->tmp_link, &dfs); } } else { list_add(&block->left->tmp_link, &dfs); list_add(&block->right->tmp_link, &dfs); } } while (1);
return ERR_PTR(-ENOSPC);
err_undo: /* * We really don't want to leave around a bunch of split blocks, since * bigger is better, so make sure we merge everything back before we * free the allocated blocks. */ __gpu_buddy_undo_splits(mm, block); return ERR_PTR(err);}
/* Return the highest-address free block of at least @order. */static struct gpu_buddy_block *get_maxblock(struct gpu_buddy *mm, unsigned int order){ struct gpu_buddy_block *max_block; struct gpu_buddy_block *block; unsigned int i;
/* * Top-down allocation is a strict address-placement policy: the block * is chosen purely by offset, regardless of its clear/dirty state. * Clear state is re-derived from the dirty tracker once the allocation * completes, and the driver is responsible for issuing the clear pass * if a clear region is required. */ max_block = NULL;
for (i = order; i <= mm->max_order; ++i) { block = rbtree_last_free_block(&mm->free_tree[i]); if (!block) continue;
if (!max_block || gpu_buddy_block_offset(block) > gpu_buddy_block_offset(max_block)) max_block = block; }
return max_block;}
static struct gpu_buddy_block *alloc_from_freetree(struct gpu_buddy *mm, unsigned int order, unsigned long flags){ struct gpu_buddy_block *block = NULL; unsigned int tmp; int err;
if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) { block = get_maxblock(mm, order); if (block) tmp = gpu_buddy_block_order(block); } else { if (flags & GPU_BUDDY_CLEAR_ALLOCATION) { for (tmp = order; tmp <= mm->max_order; ++tmp) { block = rbtree_last_clear_free_block(&mm->free_tree[tmp], GPU_BLOCK_MIXED); if (block) break; } } if (!block) { for (tmp = order; tmp <= mm->max_order; ++tmp) { block = rbtree_last_free_block(&mm->free_tree[tmp]); if (block) break; } } }
if (!block) return ERR_PTR(-ENOSPC);
BUG_ON(!gpu_buddy_block_is_free(block));
while (tmp != order) { err = split_block(mm, block); if (unlikely(err)) goto err_undo;
if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) && !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) { bool right_clear, left_clear;
right_clear = gpu_buddy_block_is_clear(block->right); left_clear = gpu_buddy_block_is_clear(block->left);
if (right_clear) block = block->right; else if (left_clear) block = block->left; else if (block->right->has_clear) block = block->right; else if (block->left->has_clear) block = block->left; else block = block->right; } else { block = block->right; } tmp--; } return block;
err_undo: __gpu_buddy_undo_splits(mm, block); return ERR_PTR(err);}
static boolgpu_buddy_can_offset_align(u64 size, u64 min_block_size){ return size < min_block_size && is_power_of_2(size);}
static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node, unsigned int alignment){ struct gpu_buddy_block *block;
block = rbtree_get_free_block(node); return block->subtree_max_alignment >= alignment;}
static struct gpu_buddy_block *gpu_buddy_find_block_aligned(struct gpu_buddy *mm, unsigned int order, unsigned int alignment){ struct rb_root *root = &mm->free_tree[order]; struct rb_node *rb = root->rb_node;
while (rb) { struct gpu_buddy_block *block = rbtree_get_free_block(rb); struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right;
if (right_node) { if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) { rb = right_node; continue; } }
if (gpu_buddy_block_offset_alignment(block) >= alignment) return block;
if (left_node) { if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) { rb = left_node; continue; } }
break; }
return NULL;}
static struct gpu_buddy_block *gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm, u64 size, u64 min_block_size){ struct gpu_buddy_block *block = NULL; unsigned int order, tmp, alignment; unsigned long pages; int err;
alignment = ilog2(min_block_size); pages = size >> ilog2(mm->chunk_size); order = fls(pages) - 1;
/* * Offset-aligned allocation is a strict address-placement policy: the * block is chosen purely by its offset alignment, regardless of its * clear/dirty state. Clear state is re-derived from the dirty tracker * once the allocation completes, and the driver is responsible for * issuing the clear pass if a clear region is required. */ for (tmp = order; tmp <= mm->max_order; ++tmp) { block = gpu_buddy_find_block_aligned(mm, tmp, alignment); if (block) break; }
if (!block) return ERR_PTR(-ENOSPC);
while (gpu_buddy_block_order(block) > order) { struct gpu_buddy_block *left, *right;
err = split_block(mm, block); if (unlikely(err)) goto err_undo;
left = block->left; right = block->right;
if (gpu_buddy_block_offset_alignment(right) >= alignment) block = right; else block = left; }
return block;
err_undo: /* * We really don't want to leave around a bunch of split blocks, since * bigger is better, so make sure we merge everything back before we * free the allocated blocks. */ __gpu_buddy_undo_splits(mm, block); return ERR_PTR(err);}
static int __alloc_range(struct gpu_buddy *mm, struct list_head *dfs, u64 start, u64 size, unsigned long flags, struct list_head *blocks, u64 *total_allocated_on_err){ struct gpu_buddy_block *block; u64 total_allocated = 0; LIST_HEAD(allocated); u64 end; int err;
end = start + size - 1;
do { u64 block_start; u64 block_end;
block = list_first_entry_or_null(dfs, struct gpu_buddy_block, tmp_link); if (!block) break;
list_del(&block->tmp_link);
block_start = gpu_buddy_block_offset(block); block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
if (!overlaps(start, end, block_start, block_end)) continue;
if (gpu_buddy_block_is_allocated(block)) { err = -ENOSPC; goto err_free; }
if (contains(start, end, block_start, block_end)) { if (gpu_buddy_block_is_free(block)) { u64 block_offset; u64 block_size;
block_size = gpu_buddy_block_size(mm, block); block_offset = gpu_buddy_block_offset(block);
if (!gpu_buddy_block_is_clear(block)) gpu_dirty_tracker_remove_range(&mm->dirty, block_offset, block_size);
mark_allocated(mm, block); total_allocated += block_size; mm->avail -= block_size;
list_add_tail(&block->link, &allocated); continue; } }
if (!gpu_buddy_block_is_split(block)) { err = split_block(mm, block); if (unlikely(err)) goto err_undo; }
list_add(&block->right->tmp_link, dfs); list_add(&block->left->tmp_link, dfs); } while (1);
if (total_allocated < size) { err = -ENOSPC; goto err_free; }
list_splice_tail(&allocated, blocks);
return 0;
err_undo: /* * We really don't want to leave around a bunch of split blocks, since * bigger is better, so make sure we merge everything back before we * free the allocated blocks. */ __gpu_buddy_undo_splits(mm, block);
err_free: if (err == -ENOSPC && total_allocated_on_err) { list_splice_tail(&allocated, blocks); *total_allocated_on_err = total_allocated; } else { gpu_buddy_free_list_internal(mm, &allocated); }
return err;}
static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, u64 start, u64 size, unsigned long flags, u64 *total_allocated_on_err, struct list_head *blocks){ LIST_HEAD(dfs); int i;
for (i = 0; i < mm->n_roots; ++i) list_add_tail(&mm->roots[i]->tmp_link, &dfs);
return __alloc_range(mm, &dfs, start, size, flags, blocks, total_allocated_on_err);}
static int __alloc_contig_aligned_retry(struct gpu_buddy *mm, u64 unaligned_offset, u64 size, u64 min_block_size, unsigned long flags, struct list_head *blocks){ u64 aligned_offset = round_down(unaligned_offset, min_block_size);
return __gpu_buddy_alloc_range(mm, aligned_offset, size, flags, NULL, blocks);}
static int __alloc_contig_try_harder(struct gpu_buddy *mm, u64 size, u64 min_block_size, unsigned long flags, struct list_head *blocks){ u64 rhs_offset, lhs_offset, filled; struct gpu_buddy_block *block; struct rb_root *root; struct rb_node *iter; unsigned long pages; unsigned int order; u64 modify_size; int err;
modify_size = rounddown_pow_of_two(size); pages = modify_size >> ilog2(mm->chunk_size); order = fls(pages) - 1; if (order == 0) return -ENOSPC;
root = &mm->free_tree[order]; if (RB_EMPTY_ROOT(root)) return -ENOSPC;
iter = rb_last(root); while (iter) { block = rbtree_get_free_block(iter);
rhs_offset = gpu_buddy_block_offset(block);
/* Allocate blocks traversing RHS */ err = __gpu_buddy_alloc_range(mm, rhs_offset, size, flags, &filled, blocks); if (err && err != -ENOSPC) return err; if (!err && IS_ALIGNED(rhs_offset, min_block_size)) return 0; if (!err) { /* Allocate the unaligned RHS offset using round_down */ gpu_buddy_free_list_internal(mm, blocks); err = __alloc_contig_aligned_retry(mm, rhs_offset, size, min_block_size, flags, blocks); if (!err) return 0; if (err != -ENOSPC) { gpu_buddy_free_list_internal(mm, blocks); return err; } goto next; }
if (size - filled > rhs_offset) goto next;
lhs_offset = rhs_offset - (size - filled);
/* Allocate the unaligned LHS offset using round_down */ gpu_buddy_free_list_internal(mm, blocks); err = __alloc_contig_aligned_retry(mm, lhs_offset, size, min_block_size, flags, blocks); if (!err) return 0; if (err != -ENOSPC) { gpu_buddy_free_list_internal(mm, blocks); return err; }next: gpu_buddy_free_list_internal(mm, blocks); iter = rb_prev(iter); }
return -ENOSPC;}
/** * gpu_buddy_block_trim - free unused pages * * @mm: GPU buddy manager * @start: start address to begin the trimming. * @new_size: original size requested * @blocks: Input and output list of allocated blocks. * MUST contain single block as input to be trimmed. * On success will contain the newly allocated blocks * making up the @new_size. Blocks always appear in * ascending order * * For contiguous allocation, we round up the size to the nearest * power of two value, drivers consume *actual* size, so remaining * portions are unused and can be optionally freed with this function * * Returns: * 0 on success, error code on failure. */int gpu_buddy_block_trim(struct gpu_buddy *mm, u64 *start, u64 new_size, struct list_head *blocks){ struct gpu_buddy_block *parent; struct gpu_buddy_block *block; u64 block_start, block_end; LIST_HEAD(dfs); bool was_clear; u64 new_start; int err;
gpu_buddy_driver_lock_held(mm);
if (!list_is_singular(blocks)) return -EINVAL;
block = list_first_entry(blocks, struct gpu_buddy_block, link);
block_start = gpu_buddy_block_offset(block); block_end = block_start + gpu_buddy_block_size(mm, block);
if (WARN_ON(!gpu_buddy_block_is_allocated(block))) return -EINVAL;
if (new_size > gpu_buddy_block_size(mm, block)) return -EINVAL;
if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) return -EINVAL;
if (new_size == gpu_buddy_block_size(mm, block)) return 0;
new_start = block_start; if (start) { new_start = *start;
if (new_start < block_start) return -EINVAL;
if (!IS_ALIGNED(new_start, mm->chunk_size)) return -EINVAL;
if (range_overflows(new_start, new_size, block_end)) return -EINVAL; }
list_del(&block->link);
was_clear = gpu_buddy_block_is_clear(block);
if (!was_clear) gpu_dirty_tracker_mark_dirty(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block));
__mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR : GPU_BLOCK_DIRTY); mm->avail += gpu_buddy_block_size(mm, block);
/* Prevent recursively freeing this node */ parent = block->parent; block->parent = NULL;
list_add(&block->tmp_link, &dfs); err = __alloc_range(mm, &dfs, new_start, new_size, was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0, blocks, NULL); if (err) { mark_allocated(mm, block); mm->avail -= gpu_buddy_block_size(mm, block); if (!was_clear) { gpu_dirty_tracker_remove_range(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block)); } if (was_clear) block->header |= GPU_BUDDY_HEADER_CLEAR; list_add(&block->link, blocks); }
block->parent = parent; return err;}EXPORT_SYMBOL(gpu_buddy_block_trim);
static bool dirty_steer_window(struct gpu_buddy *mm, u64 req_size, u64 *start, u64 *end, unsigned long *flags){ u64 aligned_start; struct gpu_dirty_extent *ext = gpu_dirty_tracker_find(&mm->dirty, req_size, &aligned_start);
if (!ext) return false;
*start = aligned_start; *end = ext->end; *flags |= GPU_BUDDY_RANGE_ALLOCATION; return true;}
static struct gpu_buddy_block *__gpu_buddy_alloc_blocks(struct gpu_buddy *mm, u64 start, u64 end, u64 size, u64 min_block_size, unsigned int order, unsigned long flags){ struct gpu_buddy_block *block; bool steered = false;
/* Allocate from dirty tracker */ if (!(flags & GPU_BUDDY_RANGE_ALLOCATION) && !(flags & GPU_BUDDY_CLEAR_ALLOCATION) && size >= min_block_size && gpu_buddy_clear_avail(mm) && mm->dirty.total_dirty) { u64 block_size = mm->chunk_size << order;
steered = dirty_steer_window(mm, block_size, &start, &end, &flags); }
if (flags & GPU_BUDDY_RANGE_ALLOCATION) { /* Allocate traversing within the range */ block = __alloc_range_bias(mm, start, end, order, flags); if (!IS_ERR(block) || !steered) return block;
flags &= ~GPU_BUDDY_RANGE_ALLOCATION; }
if (size < min_block_size) /* Allocate from an offset-aligned region without size rounding */ return gpu_buddy_offset_aligned_allocation(mm, size, min_block_size);
/* Allocate from freetree */ return alloc_from_freetree(mm, order, flags);}
/** * gpu_buddy_alloc_blocks - allocate power-of-two blocks * * @mm: GPU buddy manager to allocate from * @start: start of the allowed range for this block * @end: end of the allowed range for this block * @size: size of the allocation in bytes * @min_block_size: alignment of the allocation * @blocks: output list head to add allocated blocks * @flags: GPU_BUDDY_*_ALLOCATION flags * * alloc_range_bias() called on range limitations, which traverses * the tree and returns the desired block. * * alloc_from_freetree() called when *no* range restrictions * are enforced, which picks the block from the freetree. * * Returns: * 0 on success, error code on failure. */int gpu_buddy_alloc_blocks(struct gpu_buddy *mm, u64 start, u64 end, u64 size, u64 min_block_size, struct list_head *blocks, unsigned long flags){ struct gpu_buddy_block *block = NULL; u64 original_size, original_min_size; unsigned int min_order, order; LIST_HEAD(allocated); unsigned long pages; int err;
gpu_buddy_driver_lock_held(mm);
if (size < mm->chunk_size) return -EINVAL;
if (min_block_size < mm->chunk_size) return -EINVAL;
if (!is_power_of_2(min_block_size)) return -EINVAL;
if (!IS_ALIGNED(start | end | size, mm->chunk_size)) return -EINVAL;
if (end > mm->size) return -EINVAL;
if (range_overflows(start, size, mm->size)) return -EINVAL;
/* Actual range allocation */ if (start + size == end) { if (!IS_ALIGNED(start | end, min_block_size)) return -EINVAL;
return __gpu_buddy_alloc_range(mm, start, size, flags, NULL, blocks); }
original_size = size; original_min_size = min_block_size;
/* Roundup the size to power of 2 */ if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) { size = roundup_pow_of_two(size); min_block_size = size; /* * Normalize the requested size to min_block_size for regular allocations. * Offset-aligned allocations intentionally skip size rounding. */ } else if (!gpu_buddy_can_offset_align(size, min_block_size)) { size = round_up(size, min_block_size); }
pages = size >> ilog2(mm->chunk_size); order = fls(pages) - 1; min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
if (order > mm->max_order || size > mm->size) { if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) && !(flags & GPU_BUDDY_RANGE_ALLOCATION)) return __alloc_contig_try_harder(mm, original_size, original_min_size, flags, blocks);
return -EINVAL; }
do { order = min(order, (unsigned int)fls(pages) - 1); BUG_ON(order > mm->max_order); /* * Regular allocations must not allocate blocks smaller than min_block_size. * Offset-aligned allocations deliberately bypass this constraint. */ BUG_ON(size >= min_block_size && order < min_order);
do { block = __gpu_buddy_alloc_blocks(mm, start, end, size, min_block_size, order, flags); if (!IS_ERR(block)) break;
if (size >= min_block_size && order > min_order) { order--; continue; }
/* * Try contiguous block allocation through * try harder method. */ if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION && !(flags & GPU_BUDDY_RANGE_ALLOCATION)) { err = __alloc_contig_try_harder(mm, original_size, original_min_size, flags, blocks); if (!err) return 0; if (err != -ENOSPC) return err; goto err_free; } err = -ENOSPC; goto err_free; } while (1);
if (!gpu_buddy_block_is_clear(block)) gpu_dirty_tracker_remove_range(&mm->dirty, gpu_buddy_block_offset(block), gpu_buddy_block_size(mm, block));
mark_allocated(mm, block); mm->avail -= gpu_buddy_block_size(mm, block);
kmemleak_update_trace(block); list_add_tail(&block->link, &allocated);
pages -= BIT(order);
if (!pages) break; } while (1);
/* Trim the allocated block to the required size */ if (!(flags & GPU_BUDDY_TRIM_DISABLE) && original_size != size) { struct list_head *trim_list; LIST_HEAD(temp); u64 trim_size;
trim_list = &allocated; trim_size = original_size;
if (!list_is_singular(&allocated)) { block = list_last_entry(&allocated, typeof(*block), link); list_move(&block->link, &temp); trim_list = &temp; trim_size = gpu_buddy_block_size(mm, block) - (size - original_size); }
gpu_buddy_block_trim(mm, NULL, trim_size, trim_list);
if (!list_empty(&temp)) list_splice_tail(trim_list, &allocated); }
list_splice_tail(&allocated, blocks); return 0;
err_free: gpu_buddy_free_list_internal(mm, &allocated); return err;}EXPORT_SYMBOL(gpu_buddy_alloc_blocks);
/** * gpu_buddy_block_print - print block information * * @mm: GPU buddy manager * @block: GPU buddy block */void gpu_buddy_block_print(struct gpu_buddy *mm, struct gpu_buddy_block *block){ u64 start = gpu_buddy_block_offset(block); u64 size = gpu_buddy_block_size(mm, block);
pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size);}EXPORT_SYMBOL(gpu_buddy_block_print);
/** * gpu_buddy_print - print allocator state * * @mm: GPU buddy manager */void gpu_buddy_print(struct gpu_buddy *mm){ int order;
gpu_buddy_driver_lock_held(mm); pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, gpu_buddy_clear_avail(mm) >> 20);
for (order = mm->max_order; order >= 0; order--) { u64 free_count = mm->free_scoreboard[order]; u64 used_count = mm->used_scoreboard[order]; u64 block_size = mm->chunk_size << order; u64 free = free_count * block_size; u64 used = used_count * block_size;
if (block_size < SZ_1M) pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n", order, free >> 10, used >> 10, free_count, used_count); else pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n", order, free >> 20, used >> 20, free_count, used_count); }}EXPORT_SYMBOL(gpu_buddy_print);
static void gpu_buddy_module_exit(void){ kmem_cache_destroy(slab_extents); kmem_cache_destroy(slab_blocks);}
static int __init gpu_buddy_module_init(void){ slab_blocks = KMEM_CACHE(gpu_buddy_block, 0); if (!slab_blocks) return -ENOMEM;
slab_extents = KMEM_CACHE(gpu_dirty_extent, 0); if (!slab_extents) goto err_destroy_blocks;
return 0;
err_destroy_blocks: kmem_cache_destroy(slab_blocks); return -ENOMEM;}
module_init(gpu_buddy_module_init);module_exit(gpu_buddy_module_exit);
MODULE_DESCRIPTION("GPU Buddy Allocator");MODULE_LICENSE("Dual MIT/GPL");