Lines Matching refs:chunk
28 * There is special consideration for the first chunk which must handle
30 * are not online yet. In short, the first chunk is structured like so:
45 * The allocator tries to allocate from the fullest chunk first. Each chunk
50 * of the bitmap. The reverse mapping from page to chunk is stored in
54 * Each bit represents a fragment of size PCPU_MIN_ALLOC_SIZE. The chunk
66 * setup the first chunk containing the kernel static percpu area
140 /* the address of the first chunk which starts with the kernel static area */
153 * The first chunk which always exists. Note that unlike other
160 * Optional reserved chunk. This chunk reserves part of the first
161 * chunk and serves it for reserved allocations. When the reserved
167 static DEFINE_MUTEX(pcpu_alloc_mutex); /* chunk create/destroy, [de]pop, map ext */
169 struct list_head *pcpu_chunk_lists __ro_after_init; /* chunk list slots */
175 * The number of empty populated pages by chunk type, protected by pcpu_lock.
176 * The reserved chunk doesn't contribute to the count.
182 * pcpu_lock. This number is kept per a unit per chunk (i.e. when a page gets
183 * allocated/deallocated, it is allocated/deallocated in all units of a chunk
192 * empty chunk.
206 * pcpu_addr_in_chunk - check if the address is served from this chunk
207 * @chunk: chunk of interest
211 * True if the address is served from this chunk.
213 static bool pcpu_addr_in_chunk(struct pcpu_chunk *chunk, void *addr)
217 if (!chunk)
220 start_addr = chunk->base_addr + chunk->start_offset;
221 end_addr = chunk->base_addr + chunk->nr_pages * PAGE_SIZE -
222 chunk->end_offset;
240 static int pcpu_chunk_slot(const struct pcpu_chunk *chunk)
242 const struct pcpu_block_md *chunk_md = &chunk->chunk_md;
244 if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE ||
251 /* set the pointer to a chunk in a page struct */
257 /* obtain pointer to a chunk from a page struct */
273 static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
276 return (unsigned long)chunk->base_addr +
284 static unsigned long *pcpu_index_alloc_map(struct pcpu_chunk *chunk, int index)
286 return chunk->alloc_map +
335 * @chunk: chunk of interest
336 * @bit_off: chunk offset
344 static void pcpu_next_md_free_region(struct pcpu_chunk *chunk, int *bit_off,
352 for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
387 * @chunk: chunk of interest
390 * @bit_off: chunk offset
399 static void pcpu_next_fit_region(struct pcpu_chunk *chunk, int alloc_bits,
407 for (block = chunk->md_blocks + i; i < pcpu_chunk_nr_blocks(chunk);
447 *bit_off = pcpu_chunk_map_bits(chunk);
456 #define pcpu_for_each_md_free_region(chunk, bit_off, bits) \
457 for (pcpu_next_md_free_region((chunk), &(bit_off), &(bits)); \
458 (bit_off) < pcpu_chunk_map_bits((chunk)); \
460 pcpu_next_md_free_region((chunk), &(bit_off), &(bits)))
462 #define pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) \
463 for (pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
465 (bit_off) < pcpu_chunk_map_bits((chunk)); \
467 pcpu_next_fit_region((chunk), (alloc_bits), (align), &(bit_off), \
505 static void __pcpu_chunk_move(struct pcpu_chunk *chunk, int slot,
508 if (chunk != pcpu_reserved_chunk) {
511 pcpu_slot = pcpu_chunk_list(pcpu_chunk_type(chunk));
513 list_move(&chunk->list, &pcpu_slot[slot]);
515 list_move_tail(&chunk->list, &pcpu_slot[slot]);
519 static void pcpu_chunk_move(struct pcpu_chunk *chunk, int slot)
521 __pcpu_chunk_move(chunk, slot, true);
525 * pcpu_chunk_relocate - put chunk in the appropriate chunk slot
526 * @chunk: chunk of interest
529 * This function is called after an allocation or free changed @chunk.
530 * New slot according to the changed state is determined and @chunk is
531 * moved to the slot. Note that the reserved chunk is never put on
532 * chunk slots.
537 static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
539 int nslot = pcpu_chunk_slot(chunk);
542 __pcpu_chunk_move(chunk, nslot, oslot < nslot);
547 * @chunk: chunk of interest
554 static inline void pcpu_update_empty_pages(struct pcpu_chunk *chunk, int nr)
556 chunk->nr_empty_pop_pages += nr;
557 if (chunk != pcpu_reserved_chunk)
558 pcpu_nr_empty_pop_pages[pcpu_chunk_type(chunk)] += nr;
654 * @chunk: chunk of interest
655 * @bit_off: chunk offset
668 static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off,
680 block = chunk->md_blocks + s_index;
683 l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index), s_off);
690 * pcpu_chunk_refresh_hint - updates metadata about a chunk
691 * @chunk: chunk of interest
701 static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk, bool full_scan)
703 struct pcpu_block_md *chunk_md = &chunk->chunk_md;
718 pcpu_for_each_md_free_region(chunk, bit_off, bits)
724 * @chunk: chunk of interest
730 static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index)
732 struct pcpu_block_md *block = chunk->md_blocks + index;
733 unsigned long *alloc_map = pcpu_index_alloc_map(chunk, index);
757 * @chunk: chunk of interest
758 * @bit_off: chunk offset
762 * refreshed by a full scan iff the chunk's contig hint is broken. Block level
765 static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
768 struct pcpu_block_md *chunk_md = &chunk->chunk_md;
785 s_block = chunk->md_blocks + s_index;
786 e_block = chunk->md_blocks + e_index;
799 pcpu_index_alloc_map(chunk, s_index),
817 pcpu_block_refresh_hint(chunk, s_index);
840 pcpu_index_alloc_map(chunk, e_index),
853 pcpu_block_refresh_hint(chunk, e_index);
872 pcpu_update_empty_pages(chunk, -nr_empty_pages);
882 * The only time a full chunk scan is required is if the chunk
884 * was used and therefore the chunk contig hint is still correct.
891 pcpu_chunk_refresh_hint(chunk, false);
896 * @chunk: chunk of interest
897 * @bit_off: chunk offset
905 * A chunk update is triggered if a page becomes free, a block becomes free,
912 static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,
932 s_block = chunk->md_blocks + s_index;
933 e_block = chunk->md_blocks + e_index;
953 * remainder of the chunk is free.
955 int l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index),
964 end = find_next_bit(pcpu_index_alloc_map(chunk, e_index),
993 pcpu_update_empty_pages(chunk, nr_empty_pages);
996 * Refresh chunk metadata when the free makes a block free or spans
1002 pcpu_chunk_refresh_hint(chunk, true);
1004 pcpu_block_update(&chunk->chunk_md,
1011 * @chunk: chunk of interest
1012 * @bit_off: chunk offset
1022 static bool pcpu_is_populated(struct pcpu_chunk *chunk, int bit_off, int bits,
1031 bitmap_next_clear_region(chunk->populated, &rs, &re, page_end);
1041 * @chunk: chunk of interest
1046 * Given a chunk and an allocation spec, find the offset to begin searching
1050 * of a block or chunk, it is skipped. This errs on the side of caution
1058 static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits,
1061 struct pcpu_block_md *chunk_md = &chunk->chunk_md;
1065 * Check to see if the allocation can fit in the chunk's contig hint.
1068 * a new chunk would happen soon.
1077 pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) {
1078 if (!pop_only || pcpu_is_populated(chunk, bit_off, bits,
1086 if (bit_off == pcpu_chunk_map_bits(chunk))
1150 * @chunk: chunk of interest
1164 * Allocated addr offset in @chunk on success.
1167 static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits,
1170 struct pcpu_block_md *chunk_md = &chunk->chunk_md;
1177 oslot = pcpu_chunk_slot(chunk);
1183 pcpu_chunk_map_bits(chunk));
1184 bit_off = pcpu_find_zero_area(chunk->alloc_map, end, start, alloc_bits,
1190 pcpu_block_update_scan(chunk, area_off, area_bits);
1193 bitmap_set(chunk->alloc_map, bit_off, alloc_bits);
1196 set_bit(bit_off, chunk->bound_map);
1197 bitmap_clear(chunk->bound_map, bit_off + 1, alloc_bits - 1);
1198 set_bit(bit_off + alloc_bits, chunk->bound_map);
1200 chunk->free_bytes -= alloc_bits * PCPU_MIN_ALLOC_SIZE;
1205 chunk->alloc_map,
1206 pcpu_chunk_map_bits(chunk),
1209 pcpu_block_update_hint_alloc(chunk, bit_off, alloc_bits);
1211 pcpu_chunk_relocate(chunk, oslot);
1218 * @chunk: chunk of interest
1219 * @off: addr offset into chunk
1227 static int pcpu_free_area(struct pcpu_chunk *chunk, int off)
1229 struct pcpu_block_md *chunk_md = &chunk->chunk_md;
1233 pcpu_stats_area_dealloc(chunk);
1235 oslot = pcpu_chunk_slot(chunk);
1240 end = find_next_bit(chunk->bound_map, pcpu_chunk_map_bits(chunk),
1243 bitmap_clear(chunk->alloc_map, bit_off, bits);
1248 chunk->free_bytes += freed;
1253 pcpu_block_update_hint_free(chunk, bit_off, bits);
1255 pcpu_chunk_relocate(chunk, oslot);
1270 static void pcpu_init_md_blocks(struct pcpu_chunk *chunk)
1274 /* init the chunk's block */
1275 pcpu_init_md_block(&chunk->chunk_md, pcpu_chunk_map_bits(chunk));
1277 for (md_block = chunk->md_blocks;
1278 md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk);
1284 * pcpu_alloc_first_chunk - creates chunks that serve the first chunk
1288 * This is responsible for creating the chunks that serve the first chunk. The
1299 struct pcpu_chunk *chunk;
1317 /* allocate chunk */
1318 alloc_size = struct_size(chunk, populated,
1320 chunk = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
1321 if (!chunk)
1325 INIT_LIST_HEAD(&chunk->list);
1327 chunk->base_addr = (void *)aligned_addr;
1328 chunk->start_offset = start_offset;
1329 chunk->end_offset = region_size - chunk->start_offset - map_size;
1331 chunk->nr_pages = region_size >> PAGE_SHIFT;
1332 region_bits = pcpu_chunk_map_bits(chunk);
1334 alloc_size = BITS_TO_LONGS(region_bits) * sizeof(chunk->alloc_map[0]);
1335 chunk->alloc_map = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
1336 if (!chunk->alloc_map)
1341 BITS_TO_LONGS(region_bits + 1) * sizeof(chunk->bound_map[0]);
1342 chunk->bound_map = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
1343 if (!chunk->bound_map)
1347 alloc_size = pcpu_chunk_nr_blocks(chunk) * sizeof(chunk->md_blocks[0]);
1348 chunk->md_blocks = memblock_alloc(alloc_size, SMP_CACHE_BYTES);
1349 if (!chunk->md_blocks)
1354 /* first chunk isn't memcg-aware */
1355 chunk->obj_cgroups = NULL;
1357 pcpu_init_md_blocks(chunk);
1360 chunk->immutable = true;
1361 bitmap_fill(chunk->populated, chunk->nr_pages);
1362 chunk->nr_populated = chunk->nr_pages;
1363 chunk->nr_empty_pop_pages = chunk->nr_pages;
1365 chunk->free_bytes = map_size;
1367 if (chunk->start_offset) {
1369 offset_bits = chunk->start_offset / PCPU_MIN_ALLOC_SIZE;
1370 bitmap_set(chunk->alloc_map, 0, offset_bits);
1371 set_bit(0, chunk->bound_map);
1372 set_bit(offset_bits, chunk->bound_map);
1374 chunk->chunk_md.first_free = offset_bits;
1376 pcpu_block_update_hint_alloc(chunk, 0, offset_bits);
1379 if (chunk->end_offset) {
1381 offset_bits = chunk->end_offset / PCPU_MIN_ALLOC_SIZE;
1382 bitmap_set(chunk->alloc_map,
1383 pcpu_chunk_map_bits(chunk) - offset_bits,
1386 chunk->bound_map);
1387 set_bit(region_bits, chunk->bound_map);
1389 pcpu_block_update_hint_alloc(chunk, pcpu_chunk_map_bits(chunk)
1393 return chunk;
1398 struct pcpu_chunk *chunk;
1401 chunk = pcpu_mem_zalloc(pcpu_chunk_struct_size, gfp);
1402 if (!chunk)
1405 INIT_LIST_HEAD(&chunk->list);
1406 chunk->nr_pages = pcpu_unit_pages;
1407 region_bits = pcpu_chunk_map_bits(chunk);
1409 chunk->alloc_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits) *
1410 sizeof(chunk->alloc_map[0]), gfp);
1411 if (!chunk->alloc_map)
1414 chunk->bound_map = pcpu_mem_zalloc(BITS_TO_LONGS(region_bits + 1) *
1415 sizeof(chunk->bound_map[0]), gfp);
1416 if (!chunk->bound_map)
1419 chunk->md_blocks = pcpu_mem_zalloc(pcpu_chunk_nr_blocks(chunk) *
1420 sizeof(chunk->md_blocks[0]), gfp);
1421 if (!chunk->md_blocks)
1426 chunk->obj_cgroups =
1427 pcpu_mem_zalloc(pcpu_chunk_map_bits(chunk) *
1429 if (!chunk->obj_cgroups)
1434 pcpu_init_md_blocks(chunk);
1437 chunk->free_bytes = chunk->nr_pages * PAGE_SIZE;
1439 return chunk;
1443 pcpu_mem_free(chunk->md_blocks);
1446 pcpu_mem_free(chunk->bound_map);
1448 pcpu_mem_free(chunk->alloc_map);
1450 pcpu_mem_free(chunk);
1455 static void pcpu_free_chunk(struct pcpu_chunk *chunk)
1457 if (!chunk)
1460 pcpu_mem_free(chunk->obj_cgroups);
1462 pcpu_mem_free(chunk->md_blocks);
1463 pcpu_mem_free(chunk->bound_map);
1464 pcpu_mem_free(chunk->alloc_map);
1465 pcpu_mem_free(chunk);
1470 * @chunk: pcpu_chunk which got populated
1474 * Pages in [@page_start,@page_end) have been populated to @chunk. Update
1481 static void pcpu_chunk_populated(struct pcpu_chunk *chunk, int page_start,
1488 bitmap_set(chunk->populated, page_start, nr);
1489 chunk->nr_populated += nr;
1492 pcpu_update_empty_pages(chunk, nr);
1497 * @chunk: pcpu_chunk which got depopulated
1501 * Pages in [@page_start,@page_end) have been depopulated from @chunk.
1505 static void pcpu_chunk_depopulated(struct pcpu_chunk *chunk,
1512 bitmap_clear(chunk->populated, page_start, nr);
1513 chunk->nr_populated -= nr;
1516 pcpu_update_empty_pages(chunk, -nr);
1522 * To allow different implementations, chunk alloc/free and
1527 * pcpu_populate_chunk - populate the specified range of a chunk
1528 * pcpu_depopulate_chunk - depopulate the specified range of a chunk
1529 * pcpu_create_chunk - create a new chunk
1530 * pcpu_destroy_chunk - destroy a chunk, always preceded by full depop
1534 static int pcpu_populate_chunk(struct pcpu_chunk *chunk,
1536 static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk,
1540 static void pcpu_destroy_chunk(struct pcpu_chunk *chunk);
1551 * pcpu_chunk_addr_search - determine chunk containing specified address
1552 * @addr: address for which the chunk needs to be determined.
1558 * The address of the found chunk.
1562 /* is it in the dynamic region (first chunk)? */
1604 struct pcpu_chunk *chunk, int off,
1610 if (chunk) {
1611 chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT] = objcg;
1623 static void pcpu_memcg_free_hook(struct pcpu_chunk *chunk, int off, size_t size)
1627 if (!pcpu_is_memcg_chunk(pcpu_chunk_type(chunk)))
1630 objcg = chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT];
1631 chunk->obj_cgroups[off >> PCPU_MIN_ALLOC_SHIFT] = NULL;
1651 struct pcpu_chunk *chunk, int off,
1656 static void pcpu_memcg_free_hook(struct pcpu_chunk *chunk, int off, size_t size)
1665 * @reserved: allocate from the reserved chunk if available
1686 struct pcpu_chunk *chunk, *next;
1740 /* serve reserved allocations from the reserved chunk if available */
1742 chunk = pcpu_reserved_chunk;
1744 off = pcpu_find_block_fit(chunk, bits, bit_align, is_atomic);
1746 err = "alloc from reserved chunk failed";
1750 off = pcpu_alloc_area(chunk, bits, bit_align, off);
1754 err = "alloc from reserved chunk failed";
1761 list_for_each_entry_safe(chunk, next, &pcpu_slot[slot], list) {
1762 off = pcpu_find_block_fit(chunk, bits, bit_align,
1766 pcpu_chunk_move(chunk, 0);
1770 off = pcpu_alloc_area(chunk, bits, bit_align, off);
1780 * No space left. Create a new chunk. We don't want multiple
1782 * there's still no empty chunk after grabbing the mutex.
1790 chunk = pcpu_create_chunk(type, pcpu_gfp);
1791 if (!chunk) {
1792 err = "failed to allocate new chunk";
1797 pcpu_chunk_relocate(chunk, -1);
1805 pcpu_stats_area_alloc(chunk, size);
1815 bitmap_for_each_clear_region(chunk->populated, rs, re,
1817 WARN_ON(chunk->immutable);
1819 ret = pcpu_populate_chunk(chunk, rs, re, pcpu_gfp);
1823 pcpu_free_area(chunk, off);
1827 pcpu_chunk_populated(chunk, rs, re);
1839 memset((void *)pcpu_chunk_addr(chunk, cpu, 0) + off, 0, size);
1841 ptr = __addr_to_pcpu_ptr(chunk->base_addr + off);
1845 chunk->base_addr, off, ptr);
1847 pcpu_memcg_post_alloc_hook(objcg, chunk, off, size);
1933 * @type: chunk type
1949 struct pcpu_chunk *chunk, *next;
1959 list_for_each_entry_safe(chunk, next, free_head, list) {
1960 WARN_ON(chunk->immutable);
1963 if (chunk == list_first_entry(free_head, struct pcpu_chunk, list))
1966 list_move(&chunk->list, &to_free);
1971 list_for_each_entry_safe(chunk, next, &to_free, list) {
1974 bitmap_for_each_set_region(chunk->populated, rs, re, 0,
1975 chunk->nr_pages) {
1976 pcpu_depopulate_chunk(chunk, rs, re);
1978 pcpu_chunk_depopulated(chunk, rs, re);
1981 pcpu_destroy_chunk(chunk);
2013 list_for_each_entry(chunk, &pcpu_slot[slot], list) {
2014 nr_unpop = chunk->nr_pages - chunk->nr_populated;
2023 /* @chunk can't go away while pcpu_alloc_mutex is held */
2024 bitmap_for_each_clear_region(chunk->populated, rs, re, 0,
2025 chunk->nr_pages) {
2028 ret = pcpu_populate_chunk(chunk, rs, rs + nr, gfp);
2032 pcpu_chunk_populated(chunk, rs, rs + nr);
2045 chunk = pcpu_create_chunk(type, gfp);
2046 if (chunk) {
2048 pcpu_chunk_relocate(chunk, -1);
2061 * Call __pcpu_balance_workfn() for each chunk type.
2083 struct pcpu_chunk *chunk;
2098 chunk = pcpu_chunk_addr_search(addr);
2099 off = addr - chunk->base_addr;
2101 size = pcpu_free_area(chunk, off);
2103 pcpu_slot = pcpu_chunk_list(pcpu_chunk_type(chunk));
2105 pcpu_memcg_free_hook(chunk, off, size);
2108 if (chunk->free_bytes == pcpu_unit_size) {
2112 if (pos != chunk) {
2118 trace_percpu_free_percpu(chunk->base_addr, off, ptr);
2177 * percpu allocator has special setup for the first chunk, which currently
2183 * first chunk. But the current code reflects better how percpu allocator
2201 * aren't in the first chunk.
2203 * The address check is against full chunk sizes. pcpu_base_addr
2204 * points to the beginning of the first chunk including the
2205 * static region. Assumes good intent as the first chunk may
2348 * pcpu_setup_first_chunk - initialize the first percpu chunk
2352 * Initialize the first percpu chunk which contains the kernel static
2357 * chunk and prime the dynamic percpu allocator.
2362 * reserve after the static area in the first chunk. This reserves
2363 * the first chunk such that it's available only through reserved
2370 * allocation in the first chunk. The area between @ai->static_size +
2390 * The caller should have mapped the first chunk at @base_addr and
2393 * The first chunk will always contain a static and a dynamic region.
2394 * However, the static region is not managed by any chunk. If the first
2395 * chunk also contains a reserved region, it is served by two chunks -
2398 * The chunk serving the dynamic region is circulated in the chunk slots
2399 * and available for dynamic allocation like any other chunk.
2406 struct pcpu_chunk *chunk;
2524 pcpu_chunk_struct_size = struct_size(chunk, populated,
2530 * Allocate chunk slots. The additional last slot is for
2550 * dynamic region. The first chunk ends page aligned by
2559 * Initialize first chunk.
2561 * chunk. If the reserved_size is zero, the reserved chunk is NULL
2562 * and the dynamic region is initialized here. The first chunk,
2563 * pcpu_first_chunk, will always point to the chunk that serves
2568 chunk = pcpu_alloc_first_chunk(tmp_addr, map_size);
2570 /* init dynamic chunk if necessary */
2572 pcpu_reserved_chunk = chunk;
2577 chunk = pcpu_alloc_first_chunk(tmp_addr, map_size);
2580 /* link the first chunk in */
2581 pcpu_first_chunk = chunk;
2585 /* include all regions of the first chunk */
2642 /* pcpu_build_alloc_info() is used by both embed and page first chunk */
2803 * pcpu_embed_first_chunk - embed the first percpu chunk into bootmem
2811 * This is a helper to ease setting up embedded first percpu chunk and
2814 * If this function is used to setup the first chunk, it is allocated
2819 * This enables the first chunk to piggy back on the linear physical
2948 * pcpu_page_first_chunk - map the first chunk using PAGE_SIZE pages
2955 * chunk and can be called where pcpu_setup_first_chunk() is expected.