From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Google-Smtp-Source: AH8x226VSWS81JEjkUmn0ksJkRX6P+J4VzefeaP4B9NJo9mROBxAvijURLllRu6BkYFplve4mpaU ARC-Seal: i=1; a=rsa-sha256; t=1517783672; cv=none; d=google.com; s=arc-20160816; b=kvU5rKS2veBj7lUODxX1ISOkIcf2z5wRTVjDvYZeMnh+s8/Kp7j0dCEKFm/kxwGZjf nYTS7x6GR3GxrNvWiSYI5nP9k3nSce/wKkIqs9WgOsXFAQ7bPn124VxksQMTJbl7P1KE tjR961r7usr460SurzATTBreevkn0LQUv8bdQ2f3+B4K5q6GAee1gy6ISDIFe4dKo6It kdOkIoTvfpajYS4+QiyzqIZWDpmi/PJou1c1jen8oLlka3EwvfJCUM7fa+YB69yHpyr9 S3SbFoaDBelmOvPaVjl6tchYLMZ+aCyBVzLRfcAM1u0vP09v/zWB/3jH11ym1epSEg7k YJng== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:content-language:in-reply-to:mime-version :user-agent:date:message-id:from:references:cc:to:subject :dkim-signature:delivered-to:list-id:list-subscribe:list-unsubscribe :list-help:list-post:precedence:mailing-list :arc-authentication-results; bh=yDvB5uREqVnnerhu7rHP9nE89e8GBYy/CsHSCmOkOaQ=; b=bp1OUWyVwPDZJKNiSjGOICVIA0QQIuQSKypigZlgeqXlMOi6rdzr/TrsY56xrb3hOD d/h5iSosb6t1VeKSW9dxY3TqnXk9pXe4eUsoRBDpjMgfZhiKZ0gUSiAt1w9wpYB4upY8 U0mwA0nDW9f36R/83ujCavspUKMRVW1Z+mAt9dKnKZVEkT3gfagqCvRBC9lqvHdXJLLD BejlFrev5xNnu+FaQOQsy4MdBc9pg4ZH21/5R59l5tJZOb/JKT2JNY0qkyYyAUcEqfg1 Thw5uaNhvN/1FgeC7bDk3awc9k/fv+VDQ0rgp2OYM6ky3O2EsKWgkjzLkGxcj0JMc8e3 l7XQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@infradead.org header.s=bombadil.20170209 header.b=rjkDweHx; spf=pass (google.com: domain of kernel-hardening-return-11584-gregkh=linuxfoundation.org@lists.openwall.com designates 195.42.179.200 as permitted sender) smtp.mailfrom=kernel-hardening-return-11584-gregkh=linuxfoundation.org@lists.openwall.com Authentication-Results: mx.google.com; dkim=fail header.i=@infradead.org header.s=bombadil.20170209 header.b=rjkDweHx; spf=pass (google.com: domain of kernel-hardening-return-11584-gregkh=linuxfoundation.org@lists.openwall.com designates 195.42.179.200 as permitted sender) smtp.mailfrom=kernel-hardening-return-11584-gregkh=linuxfoundation.org@lists.openwall.com Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm List-Post: List-Help: List-Unsubscribe: List-Subscribe: Subject: Re: [PATCH 1/6] genalloc: track beginning of allocations To: Igor Stoppa , jglisse@redhat.com, keescook@chromium.org, mhocko@kernel.org, labbott@redhat.com, hch@infradead.org, willy@infradead.org Cc: cl@linux.com, linux-security-module@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com References: <20180204164732.28241-1-igor.stoppa@huawei.com> <20180204164732.28241-2-igor.stoppa@huawei.com> From: Randy Dunlap Message-ID: <60e66c5a-c1de-246f-4be8-b02cb0275da6@infradead.org> Date: Sun, 4 Feb 2018 14:34:08 -0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 In-Reply-To: <20180204164732.28241-2-igor.stoppa@huawei.com> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: =?utf-8?q?1591489766378692364?= X-GMAIL-MSGID: =?utf-8?q?1591511532683986392?= X-Mailing-List: linux-kernel@vger.kernel.org List-ID: On 02/04/2018 08:47 AM, Igor Stoppa wrote: > The genalloc library is only capable of tracking if a certain unit of > allocation is in use or not. > > It is not capable of discerning where the memory associated to an > allocation request begins and where it ends. > > The reason is that units of allocations are tracked by using a bitmap, > where each bit represents that the unit is either allocated (1) or > available (0). > > The user of the API must keep track of how much space was requested, if > it ever needs to be freed. > > This can cause errors being undetected. > Ex: > * Only a subset of the memory provided to an allocation request is freed > * The memory from a subsequent allocation is freed > * The memory being freed doesn't start at the beginning of an > allocation. > > The bitmap is used because it allows to perform lockless read/write > access, where this is supported by hw through cmpxchg. > Similarly, it is possible to scan the bitmap for a sufficiently long > sequence of zeros, to identify zones available for allocation. > > -- > > This patch doubles the space reserved in the bitmap for each allocation. > By using 2 bits per allocation, it is possible to encode also the > information of where the allocation starts: > (msb to the left, lsb to the right, in the following "dictionary") > > 11: first allocation unit in the allocation > 10: any subsequent allocation unit (if any) in the allocation > 00: available allocation unit > 01: invalid > > Ex, with the same notation as above - MSb.......LSb: > > ...000010111100000010101011 <-- Read in this direction. > \__|\__|\|\____|\______| > | | | | \___ 4 used allocation units > | | | \___________ 3 empty allocation units > | | \_________________ 1 used allocation unit > | \___________________ 2 used allocation units > \_______________________ 2 empty allocation units > > Because of the encoding, the previous lockless operations are still > possible. The only caveat is to change the parameter of the zero-finding > function which establishes the alignment at which to perform the test > for first zero. > The original value of the parameter is 0, meaning that an allocation can > start at any point in the bitmap, while the new value is 1, meaning that > allocations can start only at even places (bit 0, bit 2, etc.) > The number of zeroes to look for, must therefore be doubled. > > When it's time to free the memory associated to an allocation request, > it's a matter of checking if the corresponding allocation unit is really > the beginning of an allocation (both bits are set to 1). > Looking for the ending can also be performed locklessly. > It's sufficient to identify the first mapped allocation unit > that is represented either as free (00) or busy (11). > Even if the allocation status should change in the meanwhile, it doesn't > matter, since it can only transition between free (00) and > first-allocated (11). > > The parameter indicating to the *_free() function the size of the space > that should be freed is not currently removed, to facilitate the > transition, but it is verified, whenever it is not zero. > If it is set to zero, then the free function will autonomously decide the > size to be free, by scanning the bitmap. > > About the implementation: the patch introduces the concept of "bitmap > entry", which has a 1:1 mapping with allocation units, while the code > being patched has a 1:1 mapping between allocation units and bits. > > This means that, now, the bitmap can be extended (by following powers of > 2), to track also other properties of the allocations, if ever needed. It would be good for a lot of this to be in a source file or the pmalloc.rst documentation file instead of living only in the git repository. > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 417 ++++++++++++++++++++++++++++++++--------------- > 2 files changed, 289 insertions(+), 132 deletions(-) > > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..dde78307b093 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -36,114 +36,221 @@ > #include > #include > > +#define ENTRY_ORDER 1UL > +#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL) > +#define ENTRY_HEAD ENTRY_MASK > +#define ENTRY_UNUSED 0UL > +#define BITS_PER_ENTRY (1U << ENTRY_ORDER) > +#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER) > +#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER) > +#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG) > +#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x))) > + > +#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG) > + > +/* Binary pattern of 1010...1010 that spans one unsigned long. */ > +#define MASK (~0UL / 3 * 2) > + > +/** > + * get_bitmap_entry - extracts the specified entry from the bitmap > + * @map: pointer to a bitmap > + * @entry_index: the index of the desired entry in the bitmap > + * > + * Returns the requested bitmap. > + */ > +static inline unsigned long get_bitmap_entry(unsigned long *map, > + int entry_index) > +{ > + return (map[ENTRIES_DIV_LONGS(entry_index)] >> > + ENTRIES_TO_BITS(entry_index % ENTRIES_PER_LONG)) & > + ENTRY_MASK; > +} > + > + > +/** > + * mem_to_units - convert references to memory into orders of allocation > + * @size: amount in bytes > + * @order: pow of 2 represented by each entry in the bitmap power > + * > + * Returns the number of units representing the size. > + */ > +static inline unsigned long mem_to_units(unsigned long size, > + unsigned long order) > +{ > + return (size + (1UL << order) - 1) >> order; > +} > + > +/** > + * chunk_size - dimension of a chunk of memory can this be more explicit about which dimension? > + * @chunk: pointer to the struct describing the chunk > + * > + * Returns the size of the chunk. > + */ > static inline size_t chunk_size(const struct gen_pool_chunk *chunk) > { > return chunk->end_addr - chunk->start_addr + 1; > } > > -static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set) > + > +/** > + * set_bits_ll - according to the mask, sets the bits specified by > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to store > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int set_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > do { > - val = nval; > - if (val & mask_to_set) > + present = nval; > + if (present & mask) > return -EBUSY; > + target = present | value; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear) > + > +/** > + * cleart_bits_ll - according to the mask, clears the bits specified by clear_bits_ll > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to clear > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int clear_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > + present = nval; > + if (unlikely((present & mask) ^ value)) > + return -EBUSY; > do { > - val = nval; > - if ((val & mask_to_clear) != mask_to_clear) > + present = nval; > + if (unlikely((present & mask) ^ value)) > return -EBUSY; > + target = present & ~mask; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -/* > - * bitmap_set_ll - set the specified number of bits at the specified position > + > +/** > + * get_boundary - verify that an allocation effectively > + * starts at the given address, then measure its length. > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start_entry: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Set @nr bits start from @start in @map lock-lessly. Several user> - * can set/clear the same bitmap simultaneously without lock. If two > - * users set the same bit, one user will return remain bits, otherwise > - * return 0. > + * Returns the length of an allocation, otherwise -EINVAL if the > + * parameters do not refer to a correct allocation. > */ > -static int bitmap_set_ll(unsigned long *map, int start, int nr) > +static int get_boundary(unsigned long *map, int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_set >= 0) { > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - nr -= bits_to_set; > - bits_to_set = BITS_PER_LONG; > - mask_to_set = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_set &= BITMAP_LAST_WORD_MASK(size); > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - } > + int i; > + unsigned long bitmap_entry; > > - return 0; > + > + if (unlikely(get_bitmap_entry(map, start_entry) != ENTRY_HEAD)) > + return -EINVAL; > + for (i = start_entry + 1; i < nentries; i++) { > + bitmap_entry = get_bitmap_entry(map, i); > + if (bitmap_entry == ENTRY_HEAD || > + bitmap_entry == ENTRY_UNUSED) > + return i; > + } > + return nentries - start_entry; > } > > + > +#define SET_BITS 1 > +#define CLEAR_BITS 0 > + > /* > - * bitmap_clear_ll - clear the specified number of bits at the specified position > + * alter_bitmap_ll - set or clear the entries associated to an allocation with an allocation > + * @alteration: selection if the bits selected should be set or cleared indicates if > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Clear @nr bits start from @start in @map lock-lessly. Several users > - * can set/clear the same bitmap simultaneously without lock. If two > - * users clear the same bit, one user will return remain bits, > - * otherwise return 0. > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > + * If two users alter the same bit, one user will return remaining > + * entries, otherwise return 0. > */ > -static int bitmap_clear_ll(unsigned long *map, int start, int nr) > +static int alter_bitmap_ll(bool alteration, unsigned long *map, > + int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_clear >= 0) { > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > - nr -= bits_to_clear; > - bits_to_clear = BITS_PER_LONG; > - mask_to_clear = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_clear &= BITMAP_LAST_WORD_MASK(size); > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > + unsigned long start_bit; > + unsigned long end_bit; > + unsigned long mask; > + unsigned long value; > + int nbits; > + int bits_to_write; > + int index; > + int (*action)(unsigned long *addr, > + unsigned long mask, unsigned long value); > + > + action = (alteration == SET_BITS) ? set_bits_ll : clear_bits_ll; > + > + /* Prepare for writing the initial part of the allocation, from > + * starting entry, to the end of the UL bitmap element which > + * contains it. It might be larger than the actual allocation. > + */ Use kernel multi-line comment style. > + start_bit = ENTRIES_TO_BITS(start_entry); > + end_bit = ENTRIES_TO_BITS(start_entry + nentries); > + nbits = ENTRIES_TO_BITS(nentries); > + bits_to_write = BITS_PER_LONG - start_bit % BITS_PER_LONG; > + mask = BITMAP_FIRST_WORD_MASK(start_bit); > + /* Mark the beginning of the allocation. */ > + value = MASK | (1UL << (start_bit % BITS_PER_LONG)); > + index = BITS_DIV_LONGS(start_bit); index = BITS_DIV_LONGS (only 1 space after '=') > + > + /* Writes entries to the bitmap, as long as the reminder is > + * positive or zero. > + * Might be skipped if the entries to write do not reach the end > + * of a bitmap UL unit. > + */ Fix comment style, please. > + while (nbits >= bits_to_write) { > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + nbits -= bits_to_write; > + bits_to_write = BITS_PER_LONG; > + mask = ~0UL; > + value = MASK; > + index++; > } > > + /* Takes care of the ending part of the entries to mark. */ > + if (nbits > 0) { > + mask ^= BITMAP_FIRST_WORD_MASK((end_bit) % BITS_PER_LONG); > + bits_to_write = nbits; > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + } > return 0; > } > > + > /** > * gen_pool_create - create a new special memory pool > - * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents > + * @min_alloc_order: log base 2 of number of bytes each bitmap entry represents > * @nid: node id of the node the pool structure should be allocated on, or -1 > * > * Create a new special memory pool that can be used to manage special purpose > @@ -183,10 +290,12 @@ int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phy > size_t size, int nid) > { > struct gen_pool_chunk *chunk; > - int nbits = size >> pool->min_alloc_order; > - int nbytes = sizeof(struct gen_pool_chunk) + > - BITS_TO_LONGS(nbits) * sizeof(long); > + int nentries; > + int nbytes; > > + nentries = size >> pool->min_alloc_order; > + nbytes = sizeof(struct gen_pool_chunk) + > + ENTRIES_DIV_LONGS(nentries) * sizeof(long); > chunk = kzalloc_node(nbytes, GFP_KERNEL, nid); > if (unlikely(chunk == NULL)) > return -ENOMEM; > @@ -248,7 +357,7 @@ void gen_pool_destroy(struct gen_pool *pool) > list_del(&chunk->next_chunk); > > end_bit = chunk_size(chunk) >> order; > - bit = find_next_bit(chunk->bits, end_bit, 0); > + bit = find_next_bit(chunk->entries, end_bit, 0); > BUG_ON(bit < end_bit); > > kfree(chunk); > @@ -292,7 +401,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > struct gen_pool_chunk *chunk; > unsigned long addr = 0; > int order = pool->min_alloc_order; > - int nbits, start_bit, end_bit, remain; > + int nentries, start_entry, end_entry, remain; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > @@ -301,29 +410,32 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > if (size == 0) > return 0; > > - nbits = (size + (1UL << order) - 1) >> order; > + nentries = mem_to_units(size, order); > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (size > atomic_long_read(&chunk->avail)) > continue; > > - start_bit = 0; > - end_bit = chunk_size(chunk) >> order; > + start_entry = 0; > + end_entry = chunk_size(chunk) >> order; > retry: > - start_bit = algo(chunk->bits, end_bit, start_bit, > - nbits, data, pool); > - if (start_bit >= end_bit) > + start_entry = algo(chunk->entries, end_entry, start_entry, > + nentries, data, pool); > + if (start_entry >= end_entry) > continue; > - remain = bitmap_set_ll(chunk->bits, start_bit, nbits); > + remain = alter_bitmap_ll(SET_BITS, chunk->entries, > + start_entry, nentries); > if (remain) { > - remain = bitmap_clear_ll(chunk->bits, start_bit, > - nbits - remain); > - BUG_ON(remain); > + remain = alter_bitmap_ll(CLEAR_BITS, > + chunk->entries, > + start_entry, > + nentries - remain); > goto retry; > } > > - addr = chunk->start_addr + ((unsigned long)start_bit << order); > - size = nbits << order; > + addr = chunk->start_addr + > + ((unsigned long)start_entry << order); > + size = nentries << order; > atomic_long_sub(size, &chunk->avail); > break; > } > @@ -365,7 +477,7 @@ EXPORT_SYMBOL(gen_pool_dma_alloc); > * gen_pool_free - free allocated special memory back to the pool > * @pool: pool to free to > * @addr: starting address of memory to free back to pool > - * @size: size in bytes of memory to free > + * @size: size in bytes of memory to free or 0, for auto-detection > * > * Free previously allocated special memory back to the specified > * pool. Can not be used in NMI handler on architectures without > @@ -375,22 +487,29 @@ void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size) > { > struct gen_pool_chunk *chunk; > int order = pool->min_alloc_order; > - int start_bit, nbits, remain; > + int start_entry, remaining_entries, nentries, remain; > + int boundary; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > #endif > > - nbits = (size + (1UL << order) - 1) >> order; > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (addr >= chunk->start_addr && addr <= chunk->end_addr) { > BUG_ON(addr + size - 1 > chunk->end_addr); > - start_bit = (addr - chunk->start_addr) >> order; > - remain = bitmap_clear_ll(chunk->bits, start_bit, nbits); > + start_entry = (addr - chunk->start_addr) >> order; > + remaining_entries = (chunk->end_addr - addr) >> order; > + boundary = get_boundary(chunk->entries, start_entry, > + remaining_entries); > + BUG_ON(boundary < 0); > + nentries = boundary - start_entry; > + BUG_ON(size && > + (nentries != mem_to_units(size, order))); > + remain = alter_bitmap_ll(CLEAR_BITS, chunk->entries, > + start_entry, nentries); > BUG_ON(remain); > - size = nbits << order; > - atomic_long_add(size, &chunk->avail); > + atomic_long_add(nentries << order, &chunk->avail); > rcu_read_unlock(); > return; > } > @@ -517,9 +636,9 @@ EXPORT_SYMBOL(gen_pool_set_algo); > * gen_pool_first_fit - find the first available region > * of memory matching the size requirement (no alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -527,7 +646,15 @@ unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - return bitmap_find_next_zero_area(map, size, start, nr, 0); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit); > > @@ -535,9 +662,9 @@ EXPORT_SYMBOL(gen_pool_first_fit); > * gen_pool_first_fit_align - find the first available region > * of memory matching the size requirement (alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -547,21 +674,28 @@ unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > { > struct genpool_data_align *alignment; > unsigned long align_mask; > + unsigned long bit_index; > int order; > > alignment = data; > order = pool->min_alloc_order; > - align_mask = ((alignment->align + (1UL << order) - 1) >> order) - 1; > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + align_mask = roundup_pow_of_two( > + ENTRIES_TO_BITS(mem_to_units(alignment->align, > + order))) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_align); > > /** > * gen_pool_fixed_alloc - reserve a specific region > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -571,20 +705,23 @@ unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > { > struct genpool_data_fixed *fixed_data; > int order; > - unsigned long offset_bit; > - unsigned long start_bit; > + unsigned long offset; > + unsigned long align_mask; > + unsigned long bit_index; > > fixed_data = data; > order = pool->min_alloc_order; > - offset_bit = fixed_data->offset >> order; > if (WARN_ON(fixed_data->offset & ((1UL << order) - 1))) > return size; > + offset = fixed_data->offset >> order; > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start + offset), > + ENTRIES_TO_BITS(nr), align_mask); > + if (bit_index != ENTRIES_TO_BITS(offset)) > + return size; > > - start_bit = bitmap_find_next_zero_area(map, size, > - start + offset_bit, nr, 0); > - if (start_bit != offset_bit) > - start_bit = size; > - return start_bit; > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_fixed_alloc); > > @@ -593,9 +730,9 @@ EXPORT_SYMBOL(gen_pool_fixed_alloc); > * of memory matching the size requirement. The region will be aligned > * to the order of the size specified. > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -603,9 +740,15 @@ unsigned long gen_pool_first_fit_order_align(unsigned long *map, > unsigned long size, unsigned long start, > unsigned int nr, void *data, struct gen_pool *pool) > { > - unsigned long align_mask = roundup_pow_of_two(nr) - 1; > - > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(ENTRIES_TO_BITS(nr)) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_order_align); > > @@ -613,9 +756,9 @@ EXPORT_SYMBOL(gen_pool_first_fit_order_align); > * gen_pool_best_fit - find the best fitting region of memory > * macthing the size requirement (no alignment constraint) * matching (if you don't mind fixing that also) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > * -- ~Randy From mboxrd@z Thu Jan 1 00:00:00 1970 From: rdunlap@infradead.org (Randy Dunlap) Date: Sun, 4 Feb 2018 14:34:08 -0800 Subject: [PATCH 1/6] genalloc: track beginning of allocations In-Reply-To: <20180204164732.28241-2-igor.stoppa@huawei.com> References: <20180204164732.28241-1-igor.stoppa@huawei.com> <20180204164732.28241-2-igor.stoppa@huawei.com> Message-ID: <60e66c5a-c1de-246f-4be8-b02cb0275da6@infradead.org> To: linux-security-module@vger.kernel.org List-Id: linux-security-module.vger.kernel.org On 02/04/2018 08:47 AM, Igor Stoppa wrote: > The genalloc library is only capable of tracking if a certain unit of > allocation is in use or not. > > It is not capable of discerning where the memory associated to an > allocation request begins and where it ends. > > The reason is that units of allocations are tracked by using a bitmap, > where each bit represents that the unit is either allocated (1) or > available (0). > > The user of the API must keep track of how much space was requested, if > it ever needs to be freed. > > This can cause errors being undetected. > Ex: > * Only a subset of the memory provided to an allocation request is freed > * The memory from a subsequent allocation is freed > * The memory being freed doesn't start at the beginning of an > allocation. > > The bitmap is used because it allows to perform lockless read/write > access, where this is supported by hw through cmpxchg. > Similarly, it is possible to scan the bitmap for a sufficiently long > sequence of zeros, to identify zones available for allocation. > > -- > > This patch doubles the space reserved in the bitmap for each allocation. > By using 2 bits per allocation, it is possible to encode also the > information of where the allocation starts: > (msb to the left, lsb to the right, in the following "dictionary") > > 11: first allocation unit in the allocation > 10: any subsequent allocation unit (if any) in the allocation > 00: available allocation unit > 01: invalid > > Ex, with the same notation as above - MSb.......LSb: > > ...000010111100000010101011 <-- Read in this direction. > \__|\__|\|\____|\______| > | | | | \___ 4 used allocation units > | | | \___________ 3 empty allocation units > | | \_________________ 1 used allocation unit > | \___________________ 2 used allocation units > \_______________________ 2 empty allocation units > > Because of the encoding, the previous lockless operations are still > possible. The only caveat is to change the parameter of the zero-finding > function which establishes the alignment at which to perform the test > for first zero. > The original value of the parameter is 0, meaning that an allocation can > start at any point in the bitmap, while the new value is 1, meaning that > allocations can start only at even places (bit 0, bit 2, etc.) > The number of zeroes to look for, must therefore be doubled. > > When it's time to free the memory associated to an allocation request, > it's a matter of checking if the corresponding allocation unit is really > the beginning of an allocation (both bits are set to 1). > Looking for the ending can also be performed locklessly. > It's sufficient to identify the first mapped allocation unit > that is represented either as free (00) or busy (11). > Even if the allocation status should change in the meanwhile, it doesn't > matter, since it can only transition between free (00) and > first-allocated (11). > > The parameter indicating to the *_free() function the size of the space > that should be freed is not currently removed, to facilitate the > transition, but it is verified, whenever it is not zero. > If it is set to zero, then the free function will autonomously decide the > size to be free, by scanning the bitmap. > > About the implementation: the patch introduces the concept of "bitmap > entry", which has a 1:1 mapping with allocation units, while the code > being patched has a 1:1 mapping between allocation units and bits. > > This means that, now, the bitmap can be extended (by following powers of > 2), to track also other properties of the allocations, if ever needed. It would be good for a lot of this to be in a source file or the pmalloc.rst documentation file instead of living only in the git repository. > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 417 ++++++++++++++++++++++++++++++++--------------- > 2 files changed, 289 insertions(+), 132 deletions(-) > > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..dde78307b093 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -36,114 +36,221 @@ > #include > #include > > +#define ENTRY_ORDER 1UL > +#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL) > +#define ENTRY_HEAD ENTRY_MASK > +#define ENTRY_UNUSED 0UL > +#define BITS_PER_ENTRY (1U << ENTRY_ORDER) > +#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER) > +#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER) > +#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG) > +#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x))) > + > +#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG) > + > +/* Binary pattern of 1010...1010 that spans one unsigned long. */ > +#define MASK (~0UL / 3 * 2) > + > +/** > + * get_bitmap_entry - extracts the specified entry from the bitmap > + * @map: pointer to a bitmap > + * @entry_index: the index of the desired entry in the bitmap > + * > + * Returns the requested bitmap. > + */ > +static inline unsigned long get_bitmap_entry(unsigned long *map, > + int entry_index) > +{ > + return (map[ENTRIES_DIV_LONGS(entry_index)] >> > + ENTRIES_TO_BITS(entry_index % ENTRIES_PER_LONG)) & > + ENTRY_MASK; > +} > + > + > +/** > + * mem_to_units - convert references to memory into orders of allocation > + * @size: amount in bytes > + * @order: pow of 2 represented by each entry in the bitmap power > + * > + * Returns the number of units representing the size. > + */ > +static inline unsigned long mem_to_units(unsigned long size, > + unsigned long order) > +{ > + return (size + (1UL << order) - 1) >> order; > +} > + > +/** > + * chunk_size - dimension of a chunk of memory can this be more explicit about which dimension? > + * @chunk: pointer to the struct describing the chunk > + * > + * Returns the size of the chunk. > + */ > static inline size_t chunk_size(const struct gen_pool_chunk *chunk) > { > return chunk->end_addr - chunk->start_addr + 1; > } > > -static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set) > + > +/** > + * set_bits_ll - according to the mask, sets the bits specified by > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to store > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int set_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > do { > - val = nval; > - if (val & mask_to_set) > + present = nval; > + if (present & mask) > return -EBUSY; > + target = present | value; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear) > + > +/** > + * cleart_bits_ll - according to the mask, clears the bits specified by clear_bits_ll > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to clear > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int clear_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > + present = nval; > + if (unlikely((present & mask) ^ value)) > + return -EBUSY; > do { > - val = nval; > - if ((val & mask_to_clear) != mask_to_clear) > + present = nval; > + if (unlikely((present & mask) ^ value)) > return -EBUSY; > + target = present & ~mask; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -/* > - * bitmap_set_ll - set the specified number of bits at the specified position > + > +/** > + * get_boundary - verify that an allocation effectively > + * starts at the given address, then measure its length. > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start_entry: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Set @nr bits start from @start in @map lock-lessly. Several user> - * can set/clear the same bitmap simultaneously without lock. If two > - * users set the same bit, one user will return remain bits, otherwise > - * return 0. > + * Returns the length of an allocation, otherwise -EINVAL if the > + * parameters do not refer to a correct allocation. > */ > -static int bitmap_set_ll(unsigned long *map, int start, int nr) > +static int get_boundary(unsigned long *map, int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_set >= 0) { > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - nr -= bits_to_set; > - bits_to_set = BITS_PER_LONG; > - mask_to_set = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_set &= BITMAP_LAST_WORD_MASK(size); > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - } > + int i; > + unsigned long bitmap_entry; > > - return 0; > + > + if (unlikely(get_bitmap_entry(map, start_entry) != ENTRY_HEAD)) > + return -EINVAL; > + for (i = start_entry + 1; i < nentries; i++) { > + bitmap_entry = get_bitmap_entry(map, i); > + if (bitmap_entry == ENTRY_HEAD || > + bitmap_entry == ENTRY_UNUSED) > + return i; > + } > + return nentries - start_entry; > } > > + > +#define SET_BITS 1 > +#define CLEAR_BITS 0 > + > /* > - * bitmap_clear_ll - clear the specified number of bits at the specified position > + * alter_bitmap_ll - set or clear the entries associated to an allocation with an allocation > + * @alteration: selection if the bits selected should be set or cleared indicates if > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Clear @nr bits start from @start in @map lock-lessly. Several users > - * can set/clear the same bitmap simultaneously without lock. If two > - * users clear the same bit, one user will return remain bits, > - * otherwise return 0. > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > + * If two users alter the same bit, one user will return remaining > + * entries, otherwise return 0. > */ > -static int bitmap_clear_ll(unsigned long *map, int start, int nr) > +static int alter_bitmap_ll(bool alteration, unsigned long *map, > + int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_clear >= 0) { > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > - nr -= bits_to_clear; > - bits_to_clear = BITS_PER_LONG; > - mask_to_clear = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_clear &= BITMAP_LAST_WORD_MASK(size); > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > + unsigned long start_bit; > + unsigned long end_bit; > + unsigned long mask; > + unsigned long value; > + int nbits; > + int bits_to_write; > + int index; > + int (*action)(unsigned long *addr, > + unsigned long mask, unsigned long value); > + > + action = (alteration == SET_BITS) ? set_bits_ll : clear_bits_ll; > + > + /* Prepare for writing the initial part of the allocation, from > + * starting entry, to the end of the UL bitmap element which > + * contains it. It might be larger than the actual allocation. > + */ Use kernel multi-line comment style. > + start_bit = ENTRIES_TO_BITS(start_entry); > + end_bit = ENTRIES_TO_BITS(start_entry + nentries); > + nbits = ENTRIES_TO_BITS(nentries); > + bits_to_write = BITS_PER_LONG - start_bit % BITS_PER_LONG; > + mask = BITMAP_FIRST_WORD_MASK(start_bit); > + /* Mark the beginning of the allocation. */ > + value = MASK | (1UL << (start_bit % BITS_PER_LONG)); > + index = BITS_DIV_LONGS(start_bit); index = BITS_DIV_LONGS (only 1 space after '=') > + > + /* Writes entries to the bitmap, as long as the reminder is > + * positive or zero. > + * Might be skipped if the entries to write do not reach the end > + * of a bitmap UL unit. > + */ Fix comment style, please. > + while (nbits >= bits_to_write) { > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + nbits -= bits_to_write; > + bits_to_write = BITS_PER_LONG; > + mask = ~0UL; > + value = MASK; > + index++; > } > > + /* Takes care of the ending part of the entries to mark. */ > + if (nbits > 0) { > + mask ^= BITMAP_FIRST_WORD_MASK((end_bit) % BITS_PER_LONG); > + bits_to_write = nbits; > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + } > return 0; > } > > + > /** > * gen_pool_create - create a new special memory pool > - * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents > + * @min_alloc_order: log base 2 of number of bytes each bitmap entry represents > * @nid: node id of the node the pool structure should be allocated on, or -1 > * > * Create a new special memory pool that can be used to manage special purpose > @@ -183,10 +290,12 @@ int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phy > size_t size, int nid) > { > struct gen_pool_chunk *chunk; > - int nbits = size >> pool->min_alloc_order; > - int nbytes = sizeof(struct gen_pool_chunk) + > - BITS_TO_LONGS(nbits) * sizeof(long); > + int nentries; > + int nbytes; > > + nentries = size >> pool->min_alloc_order; > + nbytes = sizeof(struct gen_pool_chunk) + > + ENTRIES_DIV_LONGS(nentries) * sizeof(long); > chunk = kzalloc_node(nbytes, GFP_KERNEL, nid); > if (unlikely(chunk == NULL)) > return -ENOMEM; > @@ -248,7 +357,7 @@ void gen_pool_destroy(struct gen_pool *pool) > list_del(&chunk->next_chunk); > > end_bit = chunk_size(chunk) >> order; > - bit = find_next_bit(chunk->bits, end_bit, 0); > + bit = find_next_bit(chunk->entries, end_bit, 0); > BUG_ON(bit < end_bit); > > kfree(chunk); > @@ -292,7 +401,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > struct gen_pool_chunk *chunk; > unsigned long addr = 0; > int order = pool->min_alloc_order; > - int nbits, start_bit, end_bit, remain; > + int nentries, start_entry, end_entry, remain; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > @@ -301,29 +410,32 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > if (size == 0) > return 0; > > - nbits = (size + (1UL << order) - 1) >> order; > + nentries = mem_to_units(size, order); > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (size > atomic_long_read(&chunk->avail)) > continue; > > - start_bit = 0; > - end_bit = chunk_size(chunk) >> order; > + start_entry = 0; > + end_entry = chunk_size(chunk) >> order; > retry: > - start_bit = algo(chunk->bits, end_bit, start_bit, > - nbits, data, pool); > - if (start_bit >= end_bit) > + start_entry = algo(chunk->entries, end_entry, start_entry, > + nentries, data, pool); > + if (start_entry >= end_entry) > continue; > - remain = bitmap_set_ll(chunk->bits, start_bit, nbits); > + remain = alter_bitmap_ll(SET_BITS, chunk->entries, > + start_entry, nentries); > if (remain) { > - remain = bitmap_clear_ll(chunk->bits, start_bit, > - nbits - remain); > - BUG_ON(remain); > + remain = alter_bitmap_ll(CLEAR_BITS, > + chunk->entries, > + start_entry, > + nentries - remain); > goto retry; > } > > - addr = chunk->start_addr + ((unsigned long)start_bit << order); > - size = nbits << order; > + addr = chunk->start_addr + > + ((unsigned long)start_entry << order); > + size = nentries << order; > atomic_long_sub(size, &chunk->avail); > break; > } > @@ -365,7 +477,7 @@ EXPORT_SYMBOL(gen_pool_dma_alloc); > * gen_pool_free - free allocated special memory back to the pool > * @pool: pool to free to > * @addr: starting address of memory to free back to pool > - * @size: size in bytes of memory to free > + * @size: size in bytes of memory to free or 0, for auto-detection > * > * Free previously allocated special memory back to the specified > * pool. Can not be used in NMI handler on architectures without > @@ -375,22 +487,29 @@ void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size) > { > struct gen_pool_chunk *chunk; > int order = pool->min_alloc_order; > - int start_bit, nbits, remain; > + int start_entry, remaining_entries, nentries, remain; > + int boundary; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > #endif > > - nbits = (size + (1UL << order) - 1) >> order; > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (addr >= chunk->start_addr && addr <= chunk->end_addr) { > BUG_ON(addr + size - 1 > chunk->end_addr); > - start_bit = (addr - chunk->start_addr) >> order; > - remain = bitmap_clear_ll(chunk->bits, start_bit, nbits); > + start_entry = (addr - chunk->start_addr) >> order; > + remaining_entries = (chunk->end_addr - addr) >> order; > + boundary = get_boundary(chunk->entries, start_entry, > + remaining_entries); > + BUG_ON(boundary < 0); > + nentries = boundary - start_entry; > + BUG_ON(size && > + (nentries != mem_to_units(size, order))); > + remain = alter_bitmap_ll(CLEAR_BITS, chunk->entries, > + start_entry, nentries); > BUG_ON(remain); > - size = nbits << order; > - atomic_long_add(size, &chunk->avail); > + atomic_long_add(nentries << order, &chunk->avail); > rcu_read_unlock(); > return; > } > @@ -517,9 +636,9 @@ EXPORT_SYMBOL(gen_pool_set_algo); > * gen_pool_first_fit - find the first available region > * of memory matching the size requirement (no alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -527,7 +646,15 @@ unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - return bitmap_find_next_zero_area(map, size, start, nr, 0); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit); > > @@ -535,9 +662,9 @@ EXPORT_SYMBOL(gen_pool_first_fit); > * gen_pool_first_fit_align - find the first available region > * of memory matching the size requirement (alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -547,21 +674,28 @@ unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > { > struct genpool_data_align *alignment; > unsigned long align_mask; > + unsigned long bit_index; > int order; > > alignment = data; > order = pool->min_alloc_order; > - align_mask = ((alignment->align + (1UL << order) - 1) >> order) - 1; > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + align_mask = roundup_pow_of_two( > + ENTRIES_TO_BITS(mem_to_units(alignment->align, > + order))) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_align); > > /** > * gen_pool_fixed_alloc - reserve a specific region > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -571,20 +705,23 @@ unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > { > struct genpool_data_fixed *fixed_data; > int order; > - unsigned long offset_bit; > - unsigned long start_bit; > + unsigned long offset; > + unsigned long align_mask; > + unsigned long bit_index; > > fixed_data = data; > order = pool->min_alloc_order; > - offset_bit = fixed_data->offset >> order; > if (WARN_ON(fixed_data->offset & ((1UL << order) - 1))) > return size; > + offset = fixed_data->offset >> order; > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start + offset), > + ENTRIES_TO_BITS(nr), align_mask); > + if (bit_index != ENTRIES_TO_BITS(offset)) > + return size; > > - start_bit = bitmap_find_next_zero_area(map, size, > - start + offset_bit, nr, 0); > - if (start_bit != offset_bit) > - start_bit = size; > - return start_bit; > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_fixed_alloc); > > @@ -593,9 +730,9 @@ EXPORT_SYMBOL(gen_pool_fixed_alloc); > * of memory matching the size requirement. The region will be aligned > * to the order of the size specified. > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -603,9 +740,15 @@ unsigned long gen_pool_first_fit_order_align(unsigned long *map, > unsigned long size, unsigned long start, > unsigned int nr, void *data, struct gen_pool *pool) > { > - unsigned long align_mask = roundup_pow_of_two(nr) - 1; > - > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(ENTRIES_TO_BITS(nr)) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_order_align); > > @@ -613,9 +756,9 @@ EXPORT_SYMBOL(gen_pool_first_fit_order_align); > * gen_pool_best_fit - find the best fitting region of memory > * macthing the size requirement (no alignment constraint) * matching (if you don't mind fixing that also) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > * -- ~Randy -- To unsubscribe from this list: send the line "unsubscribe linux-security-module" in the body of a message to majordomo at vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl0-f70.google.com (mail-pl0-f70.google.com [209.85.160.70]) by kanga.kvack.org (Postfix) with ESMTP id 6B27F6B0005 for ; Sun, 4 Feb 2018 17:34:14 -0500 (EST) Received: by mail-pl0-f70.google.com with SMTP id m39so9635183plg.6 for ; Sun, 04 Feb 2018 14:34:14 -0800 (PST) Received: from bombadil.infradead.org (bombadil.infradead.org. [65.50.211.133]) by mx.google.com with ESMTPS id y8-v6si4050653plt.704.2018.02.04.14.34.12 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sun, 04 Feb 2018 14:34:12 -0800 (PST) Subject: Re: [PATCH 1/6] genalloc: track beginning of allocations References: <20180204164732.28241-1-igor.stoppa@huawei.com> <20180204164732.28241-2-igor.stoppa@huawei.com> From: Randy Dunlap Message-ID: <60e66c5a-c1de-246f-4be8-b02cb0275da6@infradead.org> Date: Sun, 4 Feb 2018 14:34:08 -0800 MIME-Version: 1.0 In-Reply-To: <20180204164732.28241-2-igor.stoppa@huawei.com> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Igor Stoppa , jglisse@redhat.com, keescook@chromium.org, mhocko@kernel.org, labbott@redhat.com, hch@infradead.org, willy@infradead.org Cc: cl@linux.com, linux-security-module@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com On 02/04/2018 08:47 AM, Igor Stoppa wrote: > The genalloc library is only capable of tracking if a certain unit of > allocation is in use or not. > > It is not capable of discerning where the memory associated to an > allocation request begins and where it ends. > > The reason is that units of allocations are tracked by using a bitmap, > where each bit represents that the unit is either allocated (1) or > available (0). > > The user of the API must keep track of how much space was requested, if > it ever needs to be freed. > > This can cause errors being undetected. > Ex: > * Only a subset of the memory provided to an allocation request is freed > * The memory from a subsequent allocation is freed > * The memory being freed doesn't start at the beginning of an > allocation. > > The bitmap is used because it allows to perform lockless read/write > access, where this is supported by hw through cmpxchg. > Similarly, it is possible to scan the bitmap for a sufficiently long > sequence of zeros, to identify zones available for allocation. > > -- > > This patch doubles the space reserved in the bitmap for each allocation. > By using 2 bits per allocation, it is possible to encode also the > information of where the allocation starts: > (msb to the left, lsb to the right, in the following "dictionary") > > 11: first allocation unit in the allocation > 10: any subsequent allocation unit (if any) in the allocation > 00: available allocation unit > 01: invalid > > Ex, with the same notation as above - MSb.......LSb: > > ...000010111100000010101011 <-- Read in this direction. > \__|\__|\|\____|\______| > | | | | \___ 4 used allocation units > | | | \___________ 3 empty allocation units > | | \_________________ 1 used allocation unit > | \___________________ 2 used allocation units > \_______________________ 2 empty allocation units > > Because of the encoding, the previous lockless operations are still > possible. The only caveat is to change the parameter of the zero-finding > function which establishes the alignment at which to perform the test > for first zero. > The original value of the parameter is 0, meaning that an allocation can > start at any point in the bitmap, while the new value is 1, meaning that > allocations can start only at even places (bit 0, bit 2, etc.) > The number of zeroes to look for, must therefore be doubled. > > When it's time to free the memory associated to an allocation request, > it's a matter of checking if the corresponding allocation unit is really > the beginning of an allocation (both bits are set to 1). > Looking for the ending can also be performed locklessly. > It's sufficient to identify the first mapped allocation unit > that is represented either as free (00) or busy (11). > Even if the allocation status should change in the meanwhile, it doesn't > matter, since it can only transition between free (00) and > first-allocated (11). > > The parameter indicating to the *_free() function the size of the space > that should be freed is not currently removed, to facilitate the > transition, but it is verified, whenever it is not zero. > If it is set to zero, then the free function will autonomously decide the > size to be free, by scanning the bitmap. > > About the implementation: the patch introduces the concept of "bitmap > entry", which has a 1:1 mapping with allocation units, while the code > being patched has a 1:1 mapping between allocation units and bits. > > This means that, now, the bitmap can be extended (by following powers of > 2), to track also other properties of the allocations, if ever needed. It would be good for a lot of this to be in a source file or the pmalloc.rst documentation file instead of living only in the git repository. > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 417 ++++++++++++++++++++++++++++++++--------------- > 2 files changed, 289 insertions(+), 132 deletions(-) > > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..dde78307b093 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -36,114 +36,221 @@ > #include > #include > > +#define ENTRY_ORDER 1UL > +#define ENTRY_MASK ((1UL << ((ENTRY_ORDER) + 1UL)) - 1UL) > +#define ENTRY_HEAD ENTRY_MASK > +#define ENTRY_UNUSED 0UL > +#define BITS_PER_ENTRY (1U << ENTRY_ORDER) > +#define BITS_DIV_ENTRIES(x) ((x) >> ENTRY_ORDER) > +#define ENTRIES_TO_BITS(x) ((x) << ENTRY_ORDER) > +#define BITS_DIV_LONGS(x) ((x) / BITS_PER_LONG) > +#define ENTRIES_DIV_LONGS(x) (BITS_DIV_LONGS(ENTRIES_TO_BITS(x))) > + > +#define ENTRIES_PER_LONG BITS_DIV_ENTRIES(BITS_PER_LONG) > + > +/* Binary pattern of 1010...1010 that spans one unsigned long. */ > +#define MASK (~0UL / 3 * 2) > + > +/** > + * get_bitmap_entry - extracts the specified entry from the bitmap > + * @map: pointer to a bitmap > + * @entry_index: the index of the desired entry in the bitmap > + * > + * Returns the requested bitmap. > + */ > +static inline unsigned long get_bitmap_entry(unsigned long *map, > + int entry_index) > +{ > + return (map[ENTRIES_DIV_LONGS(entry_index)] >> > + ENTRIES_TO_BITS(entry_index % ENTRIES_PER_LONG)) & > + ENTRY_MASK; > +} > + > + > +/** > + * mem_to_units - convert references to memory into orders of allocation > + * @size: amount in bytes > + * @order: pow of 2 represented by each entry in the bitmap power > + * > + * Returns the number of units representing the size. > + */ > +static inline unsigned long mem_to_units(unsigned long size, > + unsigned long order) > +{ > + return (size + (1UL << order) - 1) >> order; > +} > + > +/** > + * chunk_size - dimension of a chunk of memory can this be more explicit about which dimension? > + * @chunk: pointer to the struct describing the chunk > + * > + * Returns the size of the chunk. > + */ > static inline size_t chunk_size(const struct gen_pool_chunk *chunk) > { > return chunk->end_addr - chunk->start_addr + 1; > } > > -static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set) > + > +/** > + * set_bits_ll - according to the mask, sets the bits specified by > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to store > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int set_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > do { > - val = nval; > - if (val & mask_to_set) > + present = nval; > + if (present & mask) > return -EBUSY; > + target = present | value; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear) > + > +/** > + * cleart_bits_ll - according to the mask, clears the bits specified by clear_bits_ll > + * value, at the address specified. > + * @addr: where to write > + * @mask: filter to apply for the bits to alter > + * @value: actual configuration of bits to clear > + * > + * Returns 0 upon success, -EBUSY otherwise > + */ > +static int clear_bits_ll(unsigned long *addr, > + unsigned long mask, unsigned long value) > { > - unsigned long val, nval; > + unsigned long nval; > + unsigned long present; > + unsigned long target; > > nval = *addr; > + present = nval; > + if (unlikely((present & mask) ^ value)) > + return -EBUSY; > do { > - val = nval; > - if ((val & mask_to_clear) != mask_to_clear) > + present = nval; > + if (unlikely((present & mask) ^ value)) > return -EBUSY; > + target = present & ~mask; > cpu_relax(); > - } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val); > - > + } while ((nval = cmpxchg(addr, present, target)) != target); > return 0; > } > > -/* > - * bitmap_set_ll - set the specified number of bits at the specified position > + > +/** > + * get_boundary - verify that an allocation effectively > + * starts at the given address, then measure its length. > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start_entry: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Set @nr bits start from @start in @map lock-lessly. Several user> - * can set/clear the same bitmap simultaneously without lock. If two > - * users set the same bit, one user will return remain bits, otherwise > - * return 0. > + * Returns the length of an allocation, otherwise -EINVAL if the > + * parameters do not refer to a correct allocation. > */ > -static int bitmap_set_ll(unsigned long *map, int start, int nr) > +static int get_boundary(unsigned long *map, int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_set >= 0) { > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - nr -= bits_to_set; > - bits_to_set = BITS_PER_LONG; > - mask_to_set = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_set &= BITMAP_LAST_WORD_MASK(size); > - if (set_bits_ll(p, mask_to_set)) > - return nr; > - } > + int i; > + unsigned long bitmap_entry; > > - return 0; > + > + if (unlikely(get_bitmap_entry(map, start_entry) != ENTRY_HEAD)) > + return -EINVAL; > + for (i = start_entry + 1; i < nentries; i++) { > + bitmap_entry = get_bitmap_entry(map, i); > + if (bitmap_entry == ENTRY_HEAD || > + bitmap_entry == ENTRY_UNUSED) > + return i; > + } > + return nentries - start_entry; > } > > + > +#define SET_BITS 1 > +#define CLEAR_BITS 0 > + > /* > - * bitmap_clear_ll - clear the specified number of bits at the specified position > + * alter_bitmap_ll - set or clear the entries associated to an allocation with an allocation > + * @alteration: selection if the bits selected should be set or cleared indicates if > * @map: pointer to a bitmap > - * @start: a bit position in @map > - * @nr: number of bits to set > + * @start: the index of the first entry in the bitmap > + * @nentries: number of entries to alter > * > - * Clear @nr bits start from @start in @map lock-lessly. Several users > - * can set/clear the same bitmap simultaneously without lock. If two > - * users clear the same bit, one user will return remain bits, > - * otherwise return 0. > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > + * If two users alter the same bit, one user will return remaining > + * entries, otherwise return 0. > */ > -static int bitmap_clear_ll(unsigned long *map, int start, int nr) > +static int alter_bitmap_ll(bool alteration, unsigned long *map, > + int start_entry, int nentries) > { > - unsigned long *p = map + BIT_WORD(start); > - const int size = start + nr; > - int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > - unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > - > - while (nr - bits_to_clear >= 0) { > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > - nr -= bits_to_clear; > - bits_to_clear = BITS_PER_LONG; > - mask_to_clear = ~0UL; > - p++; > - } > - if (nr) { > - mask_to_clear &= BITMAP_LAST_WORD_MASK(size); > - if (clear_bits_ll(p, mask_to_clear)) > - return nr; > + unsigned long start_bit; > + unsigned long end_bit; > + unsigned long mask; > + unsigned long value; > + int nbits; > + int bits_to_write; > + int index; > + int (*action)(unsigned long *addr, > + unsigned long mask, unsigned long value); > + > + action = (alteration == SET_BITS) ? set_bits_ll : clear_bits_ll; > + > + /* Prepare for writing the initial part of the allocation, from > + * starting entry, to the end of the UL bitmap element which > + * contains it. It might be larger than the actual allocation. > + */ Use kernel multi-line comment style. > + start_bit = ENTRIES_TO_BITS(start_entry); > + end_bit = ENTRIES_TO_BITS(start_entry + nentries); > + nbits = ENTRIES_TO_BITS(nentries); > + bits_to_write = BITS_PER_LONG - start_bit % BITS_PER_LONG; > + mask = BITMAP_FIRST_WORD_MASK(start_bit); > + /* Mark the beginning of the allocation. */ > + value = MASK | (1UL << (start_bit % BITS_PER_LONG)); > + index = BITS_DIV_LONGS(start_bit); index = BITS_DIV_LONGS (only 1 space after '=') > + > + /* Writes entries to the bitmap, as long as the reminder is > + * positive or zero. > + * Might be skipped if the entries to write do not reach the end > + * of a bitmap UL unit. > + */ Fix comment style, please. > + while (nbits >= bits_to_write) { > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + nbits -= bits_to_write; > + bits_to_write = BITS_PER_LONG; > + mask = ~0UL; > + value = MASK; > + index++; > } > > + /* Takes care of the ending part of the entries to mark. */ > + if (nbits > 0) { > + mask ^= BITMAP_FIRST_WORD_MASK((end_bit) % BITS_PER_LONG); > + bits_to_write = nbits; > + if (action(map + index, mask, value & mask)) > + return BITS_DIV_ENTRIES(nbits); > + } > return 0; > } > > + > /** > * gen_pool_create - create a new special memory pool > - * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents > + * @min_alloc_order: log base 2 of number of bytes each bitmap entry represents > * @nid: node id of the node the pool structure should be allocated on, or -1 > * > * Create a new special memory pool that can be used to manage special purpose > @@ -183,10 +290,12 @@ int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phy > size_t size, int nid) > { > struct gen_pool_chunk *chunk; > - int nbits = size >> pool->min_alloc_order; > - int nbytes = sizeof(struct gen_pool_chunk) + > - BITS_TO_LONGS(nbits) * sizeof(long); > + int nentries; > + int nbytes; > > + nentries = size >> pool->min_alloc_order; > + nbytes = sizeof(struct gen_pool_chunk) + > + ENTRIES_DIV_LONGS(nentries) * sizeof(long); > chunk = kzalloc_node(nbytes, GFP_KERNEL, nid); > if (unlikely(chunk == NULL)) > return -ENOMEM; > @@ -248,7 +357,7 @@ void gen_pool_destroy(struct gen_pool *pool) > list_del(&chunk->next_chunk); > > end_bit = chunk_size(chunk) >> order; > - bit = find_next_bit(chunk->bits, end_bit, 0); > + bit = find_next_bit(chunk->entries, end_bit, 0); > BUG_ON(bit < end_bit); > > kfree(chunk); > @@ -292,7 +401,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > struct gen_pool_chunk *chunk; > unsigned long addr = 0; > int order = pool->min_alloc_order; > - int nbits, start_bit, end_bit, remain; > + int nentries, start_entry, end_entry, remain; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > @@ -301,29 +410,32 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > if (size == 0) > return 0; > > - nbits = (size + (1UL << order) - 1) >> order; > + nentries = mem_to_units(size, order); > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (size > atomic_long_read(&chunk->avail)) > continue; > > - start_bit = 0; > - end_bit = chunk_size(chunk) >> order; > + start_entry = 0; > + end_entry = chunk_size(chunk) >> order; > retry: > - start_bit = algo(chunk->bits, end_bit, start_bit, > - nbits, data, pool); > - if (start_bit >= end_bit) > + start_entry = algo(chunk->entries, end_entry, start_entry, > + nentries, data, pool); > + if (start_entry >= end_entry) > continue; > - remain = bitmap_set_ll(chunk->bits, start_bit, nbits); > + remain = alter_bitmap_ll(SET_BITS, chunk->entries, > + start_entry, nentries); > if (remain) { > - remain = bitmap_clear_ll(chunk->bits, start_bit, > - nbits - remain); > - BUG_ON(remain); > + remain = alter_bitmap_ll(CLEAR_BITS, > + chunk->entries, > + start_entry, > + nentries - remain); > goto retry; > } > > - addr = chunk->start_addr + ((unsigned long)start_bit << order); > - size = nbits << order; > + addr = chunk->start_addr + > + ((unsigned long)start_entry << order); > + size = nentries << order; > atomic_long_sub(size, &chunk->avail); > break; > } > @@ -365,7 +477,7 @@ EXPORT_SYMBOL(gen_pool_dma_alloc); > * gen_pool_free - free allocated special memory back to the pool > * @pool: pool to free to > * @addr: starting address of memory to free back to pool > - * @size: size in bytes of memory to free > + * @size: size in bytes of memory to free or 0, for auto-detection > * > * Free previously allocated special memory back to the specified > * pool. Can not be used in NMI handler on architectures without > @@ -375,22 +487,29 @@ void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size) > { > struct gen_pool_chunk *chunk; > int order = pool->min_alloc_order; > - int start_bit, nbits, remain; > + int start_entry, remaining_entries, nentries, remain; > + int boundary; > > #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG > BUG_ON(in_nmi()); > #endif > > - nbits = (size + (1UL << order) - 1) >> order; > rcu_read_lock(); > list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) { > if (addr >= chunk->start_addr && addr <= chunk->end_addr) { > BUG_ON(addr + size - 1 > chunk->end_addr); > - start_bit = (addr - chunk->start_addr) >> order; > - remain = bitmap_clear_ll(chunk->bits, start_bit, nbits); > + start_entry = (addr - chunk->start_addr) >> order; > + remaining_entries = (chunk->end_addr - addr) >> order; > + boundary = get_boundary(chunk->entries, start_entry, > + remaining_entries); > + BUG_ON(boundary < 0); > + nentries = boundary - start_entry; > + BUG_ON(size && > + (nentries != mem_to_units(size, order))); > + remain = alter_bitmap_ll(CLEAR_BITS, chunk->entries, > + start_entry, nentries); > BUG_ON(remain); > - size = nbits << order; > - atomic_long_add(size, &chunk->avail); > + atomic_long_add(nentries << order, &chunk->avail); > rcu_read_unlock(); > return; > } > @@ -517,9 +636,9 @@ EXPORT_SYMBOL(gen_pool_set_algo); > * gen_pool_first_fit - find the first available region > * of memory matching the size requirement (no alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -527,7 +646,15 @@ unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - return bitmap_find_next_zero_area(map, size, start, nr, 0); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit); > > @@ -535,9 +662,9 @@ EXPORT_SYMBOL(gen_pool_first_fit); > * gen_pool_first_fit_align - find the first available region > * of memory matching the size requirement (alignment constraint) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -547,21 +674,28 @@ unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > { > struct genpool_data_align *alignment; > unsigned long align_mask; > + unsigned long bit_index; > int order; > > alignment = data; > order = pool->min_alloc_order; > - align_mask = ((alignment->align + (1UL << order) - 1) >> order) - 1; > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + align_mask = roundup_pow_of_two( > + ENTRIES_TO_BITS(mem_to_units(alignment->align, > + order))) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_align); > > /** > * gen_pool_fixed_alloc - reserve a specific region > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: data for alignment > * @pool: pool to get order from > */ > @@ -571,20 +705,23 @@ unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > { > struct genpool_data_fixed *fixed_data; > int order; > - unsigned long offset_bit; > - unsigned long start_bit; > + unsigned long offset; > + unsigned long align_mask; > + unsigned long bit_index; > > fixed_data = data; > order = pool->min_alloc_order; > - offset_bit = fixed_data->offset >> order; > if (WARN_ON(fixed_data->offset & ((1UL << order) - 1))) > return size; > + offset = fixed_data->offset >> order; > + align_mask = roundup_pow_of_two(BITS_PER_ENTRY) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start + offset), > + ENTRIES_TO_BITS(nr), align_mask); > + if (bit_index != ENTRIES_TO_BITS(offset)) > + return size; > > - start_bit = bitmap_find_next_zero_area(map, size, > - start + offset_bit, nr, 0); > - if (start_bit != offset_bit) > - start_bit = size; > - return start_bit; > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_fixed_alloc); > > @@ -593,9 +730,9 @@ EXPORT_SYMBOL(gen_pool_fixed_alloc); > * of memory matching the size requirement. The region will be aligned > * to the order of the size specified. > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > */ > @@ -603,9 +740,15 @@ unsigned long gen_pool_first_fit_order_align(unsigned long *map, > unsigned long size, unsigned long start, > unsigned int nr, void *data, struct gen_pool *pool) > { > - unsigned long align_mask = roundup_pow_of_two(nr) - 1; > - > - return bitmap_find_next_zero_area(map, size, start, nr, align_mask); > + unsigned long align_mask; > + unsigned long bit_index; > + > + align_mask = roundup_pow_of_two(ENTRIES_TO_BITS(nr)) - 1; > + bit_index = bitmap_find_next_zero_area(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(start), > + ENTRIES_TO_BITS(nr), > + align_mask); > + return BITS_DIV_ENTRIES(bit_index); > } > EXPORT_SYMBOL(gen_pool_first_fit_order_align); > > @@ -613,9 +756,9 @@ EXPORT_SYMBOL(gen_pool_first_fit_order_align); > * gen_pool_best_fit - find the best fitting region of memory > * macthing the size requirement (no alignment constraint) * matching (if you don't mind fixing that also) > * @map: The address to base the search on > - * @size: The bitmap size in bits > - * @start: The bitnumber to start searching at > - * @nr: The number of zeroed bits we're looking for > + * @size: The number of allocation units in the bitmap > + * @start: The allocation unit to start searching at > + * @nr: The number of allocation units we're looking for > * @data: additional data - unused > * @pool: pool to find the fit region memory from > * -- ~Randy -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org