From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Google-Smtp-Source: AH8x227YO9VUOI/dR/uZU+Oc0J9kCI+9b6oP/7qjTtWTDSnDMFHh2vqF60cKBeU/5vyb1Xg7j7q/ ARC-Seal: i=1; a=rsa-sha256; t=1518352705; cv=none; d=google.com; s=arc-20160816; b=XCt+RTTqhr8Go3sUHyzgvy9ViHxYw17qhE29P+y1oqLqqzQnmwBXudWVRzNusow7AR HQhY3hjejGI8YX7GIWHevKV5u3MnMTkhQPteIaovCcItYcZ0jq/8ny/gP7jYdQUfUzMQ A2q3xJnS4xybfM3PWEmj2l0n8X0618FXce9dVnBOFl1l71xKvgi6LWjhpBtcRSC0mSKK ZGNNQsMsId0Y+CWevvhCNLHz+9p48Jh4bwEUmHFbrtM4+PCh+IS04zEJk2rgyHawnsud ky7Kf2ZGBj2SeB/e1CUlZahaI6g/L2ScE5Q2azwUmA3y9/Nro7Nf+FQAzvjHtPdbRZ7m iRKg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:user-agent:in-reply-to:content-disposition:mime-version :references:subject:cc:to:from:date:delivered-to:delivered-to :list-id:list-subscribe:list-unsubscribe:list-help:list-post :precedence:mailing-list:arc-authentication-results; bh=wvkOXew5olp4E0PuuhRvjaEfWJply8IvyFKRiTkItaw=; b=Piuqgo0y+AYYa5mJIrwL3T9MAjdKt17ThqGVMjc+1op1lFBu2NpoNUnxQ8vN7mvmgR Lag3Bw+zt95h/mGAocrVf7/PZ0Fn/wxdM7wBc8uiFfGaRgt9WRCTZj0MAemt48+MWTAA IhORd19GNbyLJ6rRYfVYDMM5xOAmiehDmVNyW3yMjvMFlUSyTR/qQRkp0xdi7heIXVcx TmeKCIOg5cUOEQi5XKX/TpMcoOES4isTvchhhiR+lb4DP3+7Uffl26ytcOPSItFsIsGS pzPCWVoX27QXT5XAZVdCYAQ2qdyUXun9gAwvie0Ql6xyrsebjWVpxTVK6V5XE50/5mlj 4ycA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of kernel-hardening-return-11703-gregkh=linuxfoundation.org@lists.openwall.com designates 195.42.179.200 as permitted sender) smtp.mailfrom=kernel-hardening-return-11703-gregkh=linuxfoundation.org@lists.openwall.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=ibm.com Authentication-Results: mx.google.com; spf=pass (google.com: domain of kernel-hardening-return-11703-gregkh=linuxfoundation.org@lists.openwall.com designates 195.42.179.200 as permitted sender) smtp.mailfrom=kernel-hardening-return-11703-gregkh=linuxfoundation.org@lists.openwall.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=ibm.com Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm List-Post: List-Help: List-Unsubscribe: List-Subscribe: Date: Sun, 11 Feb 2018 14:24:45 +0200 From: Mike Rapoport To: Igor Stoppa Cc: willy@infradead.org, rdunlap@infradead.org, corbet@lwn.net, keescook@chromium.org, mhocko@kernel.org, labbott@redhat.com, jglisse@redhat.com, hch@infradead.org, cl@linux.com, linux-security-module@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com Subject: Re: [PATCH 1/6] genalloc: track beginning of allocations References: <20180211031920.3424-1-igor.stoppa@huawei.com> <20180211031920.3424-2-igor.stoppa@huawei.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20180211031920.3424-2-igor.stoppa@huawei.com> User-Agent: Mutt/1.5.24 (2015-08-30) X-TM-AS-GCONF: 00 x-cbid: 18021112-0020-0000-0000-000003F48176 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 18021112-0021-0000-0000-000042870632 Message-Id: <20180211122444.GB13931@rapoport-lnx> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2018-02-11_06:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=9 phishscore=0 bulkscore=0 spamscore=0 clxscore=1011 lowpriorityscore=0 impostorscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1709140000 definitions=main-1802110165 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: =?utf-8?q?1592073112440630013?= X-GMAIL-MSGID: =?utf-8?q?1592108206558001883?= X-Mailing-List: linux-kernel@vger.kernel.org List-ID: On Sun, Feb 11, 2018 at 05:19:15AM +0200, 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. > Examples: > * 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, > to track their beginning. > > For details, see the documentation inside lib/genalloc.c > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 527 ++++++++++++++++++++++++++++++++++------------- > 2 files changed, 390 insertions(+), 141 deletions(-) > > diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h > index 872f930f1b06..dcaa33e74b1c 100644 > --- a/include/linux/genalloc.h > +++ b/include/linux/genalloc.h > @@ -32,7 +32,7 @@ > > #include > #include > -#include > +#include > > struct device; > struct device_node; > @@ -76,7 +76,7 @@ struct gen_pool_chunk { > phys_addr_t phys_addr; /* physical starting address of memory chunk */ > unsigned long start_addr; /* start address of memory chunk */ > unsigned long end_addr; /* end address of memory chunk (inclusive) */ > - unsigned long bits[0]; /* bitmap for allocating memory chunk */ > + unsigned long entries[0]; /* bitmap for allocating memory chunk */ > }; > > /* > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..044347163acb 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -26,6 +26,74 @@ > * > * This source code is licensed under the GNU General Public License, > * Version 2. See the file COPYING for more details. > + * > + * > + * > + * Encoding of the bitmap tracking the allocations > + * ----------------------------------------------- > + * > + * The bitmap is composed of units of allocations. > + * > + * Each unit of allocation is represented using 2 consecutive bits. > + * > + * This makes it possible to encode, for each unit of allocation, > + * information about: > + * - allocation status (busy/free) > + * - beginning of a sequennce of allocation units (first / successive) > + * > + * > + * Dictionary of allocation units (msb to the left, lsb to the right): > + * > + * 11: first allocation unit in the allocation > + * 10: any subsequent allocation unit (if any) in the allocation > + * 00: available allocation unit > + * 01: invalid > + * > + * Example, using 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 > + * > + * The encoding allows for lockless operations, such as: > + * - search for a sufficiently large range of allocation units > + * - reservation of a selected range of allocation units > + * - release of a specific allocation > + * > + * The alignment at which to perform the research for sequence of empty > + * allocation units (marked as zeros in the bitmap) is 2^1. > + * > + * This means that an allocation can start only at even places > + * (bit 0, bit 2, etc.) in the bitmap. > + * > + * Therefore, the number of zeroes to look for must be twice the number > + * of desired allocation units. > + * > + * 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 can be either set to 0, for automated > + * assessment, or it can be specified explicitly. > + * > + * In case it is specified explicitly, the value is verified agaisnt what > + * the library is tracking internally. > + * > + * If ever needed, the bitmap could be extended, assigning larger amounts > + * of bits to each allocation unit (the increase must follow powers of 2), > + * to track other properties of the allocations. > */ > > #include > @@ -36,118 +104,230 @@ > #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 > + * > + * Return: 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 Documentation/doc-guide/kernel-doc.rst recommends to to include brackets for function comments. I haven't noticed any difference in the resulting html, so I'm not sure if the brackets are actually required. > + * @size: amount in bytes > + * @order: power of 2 represented by each entry in the bitmap > + * > + * Returns the number of units representing the size. Please s/Return/Return:/ > + */ > +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, in bytes > + * @chunk: pointer to the struct describing the chunk > + * > + * Return: The size of the chunk, in bytes. > + */ > 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 > + * > + * Return: 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) > + > +/** > + * clear_bits_ll - according to the mask, clears 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 clear > + * > + * Return: 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 users > - * 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. > + * Return: 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 with an allocation > + * @alteration: indicates if the bits selected should be set or cleared > * @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 > + * > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > * > - * 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. > + * Return: If two users alter the same bit, to one it will return > + * remaining entries, to the other it will return 0. And what if there are three or four concurrent users? ;-) I believe that a more elaborate description about what happens with concurrent attempts to alter the bitmap would be really helpful. > */ > -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. > + */ > + 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); > + > + /* > + * 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. > + */ > + 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 > * memory not managed by the regular kmalloc/kfree interface. > + * > + * Return: pointer to the pool, if successful, NULL otherwise > */ > struct gen_pool *gen_pool_create(int min_alloc_order, int nid) > { > @@ -177,16 +357,18 @@ EXPORT_SYMBOL(gen_pool_create); > * > * Add a new chunk of special memory to the specified pool. > * > - * Returns 0 on success or a -ve errno on failure. > + * Return: 0 on success or a -ve errno on failure. > */ > int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phys, > 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; > @@ -209,7 +391,7 @@ EXPORT_SYMBOL(gen_pool_add_virt); > * @pool: pool to allocate from > * @addr: starting address of memory > * > - * Returns the physical address on success, or -1 on error. > + * Return: the physical address on success, or -1 on error. > */ > phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr) > { > @@ -248,7 +430,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); > @@ -267,6 +449,8 @@ EXPORT_SYMBOL(gen_pool_destroy); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size) > { > @@ -285,6 +469,8 @@ EXPORT_SYMBOL(gen_pool_alloc); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > genpool_algo_t algo, void *data) > @@ -292,7 +478,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 +487,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; > } > @@ -342,6 +531,8 @@ EXPORT_SYMBOL(gen_pool_alloc_algo); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > void *gen_pool_dma_alloc(struct gen_pool *pool, size_t size, dma_addr_t *dma) > { > @@ -365,7 +556,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 +566,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; > } > @@ -428,8 +626,9 @@ EXPORT_SYMBOL(gen_pool_for_each_chunk); > * @start: start address > * @size: size of the region > * > - * Check if the range of addresses falls within the specified pool. Returns > - * true if the entire range is contained in the pool and false otherwise. > + * Check if the range of addresses falls within the specified pool. > + * > + * Return: true if the entire range is contained in the pool, false otherwise. > */ > bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > size_t size) > @@ -455,7 +654,7 @@ bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > * gen_pool_avail - get available free space of the pool > * @pool: pool to get available free space > * > - * Return available free space of the specified pool. > + * Return: available free space of the specified pool. > */ > size_t gen_pool_avail(struct gen_pool *pool) > { > @@ -474,7 +673,7 @@ EXPORT_SYMBOL_GPL(gen_pool_avail); > * gen_pool_size - get size in bytes of memory managed by the pool > * @pool: pool to get size > * > - * Return size in bytes of memory managed by the pool. > + * Return: size in bytes of memory managed by the pool. > */ > size_t gen_pool_size(struct gen_pool *pool) > { > @@ -517,17 +716,27 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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,11 +744,13 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -547,23 +758,32 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -571,20 +791,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,60 +816,84 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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); > > /** > * gen_pool_best_fit - find the best fitting region of memory > - * macthing the size requirement (no alignment constraint) > + * 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 > * > * Iterate over the bitmap to find the smallest free region > * which we can allocate the memory. > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - unsigned long start_bit = size; > + unsigned long start_bit = ENTRIES_TO_BITS(size); > unsigned long len = size + 1; > unsigned long index; > + unsigned long align_mask; > + unsigned long bit_index; > > - index = bitmap_find_next_zero_area(map, size, start, nr, 0); > + 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); > + index = BITS_DIV_ENTRIES(bit_index); > > while (index < size) { > - int next_bit = find_next_bit(map, size, index + nr); > - if ((next_bit - index) < len) { > - len = next_bit - index; > - start_bit = index; > + int next_bit; > + > + next_bit = find_next_bit(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(index + nr)); > + if ((BITS_DIV_ENTRIES(next_bit) - index) < len) { > + len = BITS_DIV_ENTRIES(next_bit) - index; > + start_bit = ENTRIES_TO_BITS(index); > if (len == nr) > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > - index = bitmap_find_next_zero_area(map, size, > - next_bit + 1, nr, 0); > + bit_index = > + bitmap_find_next_zero_area(map, > + ENTRIES_TO_BITS(size), > + next_bit + 1, > + ENTRIES_TO_BITS(nr), > + align_mask); > + index = BITS_DIV_ENTRIES(bit_index); > } > > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > -EXPORT_SYMBOL(gen_pool_best_fit); > > static void devm_gen_pool_release(struct device *dev, void *res) > { > @@ -672,7 +919,7 @@ static int devm_gen_pool_match(struct device *dev, void *res, void *data) > * @dev: device to retrieve the gen_pool from > * @name: name of a gen_pool or NULL, identifies a particular gen_pool on device > * > - * Returns the gen_pool for the device if one is present, or NULL. > + * Return: the gen_pool for the device if one is present, or NULL. > */ > struct gen_pool *gen_pool_get(struct device *dev, const char *name) > { > @@ -696,6 +943,8 @@ EXPORT_SYMBOL_GPL(gen_pool_get); > * Create a new special memory pool that can be used to manage special purpose > * memory not managed by the regular kmalloc/kfree interface. The pool will be > * automatically destroyed by the device management code. > + * > + * Return: the address of the pool, if successful, otherwise NULL > */ > struct gen_pool *devm_gen_pool_create(struct device *dev, int min_alloc_order, > int nid, const char *name) > @@ -743,7 +992,7 @@ EXPORT_SYMBOL(devm_gen_pool_create); > * @propname: property name containing phandle(s) > * @index: index into the phandle array > * > - * Returns the pool that contains the chunk starting at the physical > + * Return: the pool that contains the chunk starting at the physical > * address of the device tree node pointed at by the phandle property, > * or NULL if not found. > */ > -- > 2.14.1 > > -- > 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 > > -- Sincerely yours, Mike. From mboxrd@z Thu Jan 1 00:00:00 1970 From: rppt@linux.vnet.ibm.com (Mike Rapoport) Date: Sun, 11 Feb 2018 14:24:45 +0200 Subject: [PATCH 1/6] genalloc: track beginning of allocations In-Reply-To: <20180211031920.3424-2-igor.stoppa@huawei.com> References: <20180211031920.3424-1-igor.stoppa@huawei.com> <20180211031920.3424-2-igor.stoppa@huawei.com> Message-ID: <20180211122444.GB13931@rapoport-lnx> To: linux-security-module@vger.kernel.org List-Id: linux-security-module.vger.kernel.org On Sun, Feb 11, 2018 at 05:19:15AM +0200, 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. > Examples: > * 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, > to track their beginning. > > For details, see the documentation inside lib/genalloc.c > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 527 ++++++++++++++++++++++++++++++++++------------- > 2 files changed, 390 insertions(+), 141 deletions(-) > > diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h > index 872f930f1b06..dcaa33e74b1c 100644 > --- a/include/linux/genalloc.h > +++ b/include/linux/genalloc.h > @@ -32,7 +32,7 @@ > > #include > #include > -#include > +#include > > struct device; > struct device_node; > @@ -76,7 +76,7 @@ struct gen_pool_chunk { > phys_addr_t phys_addr; /* physical starting address of memory chunk */ > unsigned long start_addr; /* start address of memory chunk */ > unsigned long end_addr; /* end address of memory chunk (inclusive) */ > - unsigned long bits[0]; /* bitmap for allocating memory chunk */ > + unsigned long entries[0]; /* bitmap for allocating memory chunk */ > }; > > /* > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..044347163acb 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -26,6 +26,74 @@ > * > * This source code is licensed under the GNU General Public License, > * Version 2. See the file COPYING for more details. > + * > + * > + * > + * Encoding of the bitmap tracking the allocations > + * ----------------------------------------------- > + * > + * The bitmap is composed of units of allocations. > + * > + * Each unit of allocation is represented using 2 consecutive bits. > + * > + * This makes it possible to encode, for each unit of allocation, > + * information about: > + * - allocation status (busy/free) > + * - beginning of a sequennce of allocation units (first / successive) > + * > + * > + * Dictionary of allocation units (msb to the left, lsb to the right): > + * > + * 11: first allocation unit in the allocation > + * 10: any subsequent allocation unit (if any) in the allocation > + * 00: available allocation unit > + * 01: invalid > + * > + * Example, using 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 > + * > + * The encoding allows for lockless operations, such as: > + * - search for a sufficiently large range of allocation units > + * - reservation of a selected range of allocation units > + * - release of a specific allocation > + * > + * The alignment at which to perform the research for sequence of empty > + * allocation units (marked as zeros in the bitmap) is 2^1. > + * > + * This means that an allocation can start only at even places > + * (bit 0, bit 2, etc.) in the bitmap. > + * > + * Therefore, the number of zeroes to look for must be twice the number > + * of desired allocation units. > + * > + * 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 can be either set to 0, for automated > + * assessment, or it can be specified explicitly. > + * > + * In case it is specified explicitly, the value is verified agaisnt what > + * the library is tracking internally. > + * > + * If ever needed, the bitmap could be extended, assigning larger amounts > + * of bits to each allocation unit (the increase must follow powers of 2), > + * to track other properties of the allocations. > */ > > #include > @@ -36,118 +104,230 @@ > #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 > + * > + * Return: 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 Documentation/doc-guide/kernel-doc.rst recommends to to include brackets for function comments. I haven't noticed any difference in the resulting html, so I'm not sure if the brackets are actually required. > + * @size: amount in bytes > + * @order: power of 2 represented by each entry in the bitmap > + * > + * Returns the number of units representing the size. Please s/Return/Return:/ > + */ > +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, in bytes > + * @chunk: pointer to the struct describing the chunk > + * > + * Return: The size of the chunk, in bytes. > + */ > 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 > + * > + * Return: 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) > + > +/** > + * clear_bits_ll - according to the mask, clears 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 clear > + * > + * Return: 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 users > - * 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. > + * Return: 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 with an allocation > + * @alteration: indicates if the bits selected should be set or cleared > * @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 > + * > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > * > - * 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. > + * Return: If two users alter the same bit, to one it will return > + * remaining entries, to the other it will return 0. And what if there are three or four concurrent users? ;-) I believe that a more elaborate description about what happens with concurrent attempts to alter the bitmap would be really helpful. > */ > -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. > + */ > + 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); > + > + /* > + * 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. > + */ > + 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 > * memory not managed by the regular kmalloc/kfree interface. > + * > + * Return: pointer to the pool, if successful, NULL otherwise > */ > struct gen_pool *gen_pool_create(int min_alloc_order, int nid) > { > @@ -177,16 +357,18 @@ EXPORT_SYMBOL(gen_pool_create); > * > * Add a new chunk of special memory to the specified pool. > * > - * Returns 0 on success or a -ve errno on failure. > + * Return: 0 on success or a -ve errno on failure. > */ > int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phys, > 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; > @@ -209,7 +391,7 @@ EXPORT_SYMBOL(gen_pool_add_virt); > * @pool: pool to allocate from > * @addr: starting address of memory > * > - * Returns the physical address on success, or -1 on error. > + * Return: the physical address on success, or -1 on error. > */ > phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr) > { > @@ -248,7 +430,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); > @@ -267,6 +449,8 @@ EXPORT_SYMBOL(gen_pool_destroy); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size) > { > @@ -285,6 +469,8 @@ EXPORT_SYMBOL(gen_pool_alloc); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > genpool_algo_t algo, void *data) > @@ -292,7 +478,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 +487,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; > } > @@ -342,6 +531,8 @@ EXPORT_SYMBOL(gen_pool_alloc_algo); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > void *gen_pool_dma_alloc(struct gen_pool *pool, size_t size, dma_addr_t *dma) > { > @@ -365,7 +556,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 +566,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; > } > @@ -428,8 +626,9 @@ EXPORT_SYMBOL(gen_pool_for_each_chunk); > * @start: start address > * @size: size of the region > * > - * Check if the range of addresses falls within the specified pool. Returns > - * true if the entire range is contained in the pool and false otherwise. > + * Check if the range of addresses falls within the specified pool. > + * > + * Return: true if the entire range is contained in the pool, false otherwise. > */ > bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > size_t size) > @@ -455,7 +654,7 @@ bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > * gen_pool_avail - get available free space of the pool > * @pool: pool to get available free space > * > - * Return available free space of the specified pool. > + * Return: available free space of the specified pool. > */ > size_t gen_pool_avail(struct gen_pool *pool) > { > @@ -474,7 +673,7 @@ EXPORT_SYMBOL_GPL(gen_pool_avail); > * gen_pool_size - get size in bytes of memory managed by the pool > * @pool: pool to get size > * > - * Return size in bytes of memory managed by the pool. > + * Return: size in bytes of memory managed by the pool. > */ > size_t gen_pool_size(struct gen_pool *pool) > { > @@ -517,17 +716,27 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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,11 +744,13 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -547,23 +758,32 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -571,20 +791,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,60 +816,84 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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); > > /** > * gen_pool_best_fit - find the best fitting region of memory > - * macthing the size requirement (no alignment constraint) > + * 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 > * > * Iterate over the bitmap to find the smallest free region > * which we can allocate the memory. > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - unsigned long start_bit = size; > + unsigned long start_bit = ENTRIES_TO_BITS(size); > unsigned long len = size + 1; > unsigned long index; > + unsigned long align_mask; > + unsigned long bit_index; > > - index = bitmap_find_next_zero_area(map, size, start, nr, 0); > + 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); > + index = BITS_DIV_ENTRIES(bit_index); > > while (index < size) { > - int next_bit = find_next_bit(map, size, index + nr); > - if ((next_bit - index) < len) { > - len = next_bit - index; > - start_bit = index; > + int next_bit; > + > + next_bit = find_next_bit(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(index + nr)); > + if ((BITS_DIV_ENTRIES(next_bit) - index) < len) { > + len = BITS_DIV_ENTRIES(next_bit) - index; > + start_bit = ENTRIES_TO_BITS(index); > if (len == nr) > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > - index = bitmap_find_next_zero_area(map, size, > - next_bit + 1, nr, 0); > + bit_index = > + bitmap_find_next_zero_area(map, > + ENTRIES_TO_BITS(size), > + next_bit + 1, > + ENTRIES_TO_BITS(nr), > + align_mask); > + index = BITS_DIV_ENTRIES(bit_index); > } > > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > -EXPORT_SYMBOL(gen_pool_best_fit); > > static void devm_gen_pool_release(struct device *dev, void *res) > { > @@ -672,7 +919,7 @@ static int devm_gen_pool_match(struct device *dev, void *res, void *data) > * @dev: device to retrieve the gen_pool from > * @name: name of a gen_pool or NULL, identifies a particular gen_pool on device > * > - * Returns the gen_pool for the device if one is present, or NULL. > + * Return: the gen_pool for the device if one is present, or NULL. > */ > struct gen_pool *gen_pool_get(struct device *dev, const char *name) > { > @@ -696,6 +943,8 @@ EXPORT_SYMBOL_GPL(gen_pool_get); > * Create a new special memory pool that can be used to manage special purpose > * memory not managed by the regular kmalloc/kfree interface. The pool will be > * automatically destroyed by the device management code. > + * > + * Return: the address of the pool, if successful, otherwise NULL > */ > struct gen_pool *devm_gen_pool_create(struct device *dev, int min_alloc_order, > int nid, const char *name) > @@ -743,7 +992,7 @@ EXPORT_SYMBOL(devm_gen_pool_create); > * @propname: property name containing phandle(s) > * @index: index into the phandle array > * > - * Returns the pool that contains the chunk starting at the physical > + * Return: the pool that contains the chunk starting at the physical > * address of the device tree node pointed at by the phandle property, > * or NULL if not found. > */ > -- > 2.14.1 > > -- > To unsubscribe, send a message with 'unsubscribe linux-mm' in > the body to majordomo at kvack.org. For more info on Linux MM, > see: http://www.linux-mm.org/ . > Don't email: email at kvack.org > > -- Sincerely yours, Mike. -- 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-qk0-f198.google.com (mail-qk0-f198.google.com [209.85.220.198]) by kanga.kvack.org (Postfix) with ESMTP id 5A0546B0003 for ; Sun, 11 Feb 2018 07:25:00 -0500 (EST) Received: by mail-qk0-f198.google.com with SMTP id v68so11160430qki.13 for ; Sun, 11 Feb 2018 04:25:00 -0800 (PST) Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com. [148.163.156.1]) by mx.google.com with ESMTPS id c55si474366qte.355.2018.02.11.04.24.57 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 11 Feb 2018 04:24:58 -0800 (PST) Received: from pps.filterd (m0098394.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w1BCOWN9105583 for ; Sun, 11 Feb 2018 07:24:57 -0500 Received: from e06smtp15.uk.ibm.com (e06smtp15.uk.ibm.com [195.75.94.111]) by mx0a-001b2d01.pphosted.com with ESMTP id 2g2jv0bs74-1 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=NOT) for ; Sun, 11 Feb 2018 07:24:56 -0500 Received: from localhost by e06smtp15.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Sun, 11 Feb 2018 12:24:53 -0000 Date: Sun, 11 Feb 2018 14:24:45 +0200 From: Mike Rapoport Subject: Re: [PATCH 1/6] genalloc: track beginning of allocations References: <20180211031920.3424-1-igor.stoppa@huawei.com> <20180211031920.3424-2-igor.stoppa@huawei.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20180211031920.3424-2-igor.stoppa@huawei.com> Message-Id: <20180211122444.GB13931@rapoport-lnx> Sender: owner-linux-mm@kvack.org List-ID: To: Igor Stoppa Cc: willy@infradead.org, rdunlap@infradead.org, corbet@lwn.net, keescook@chromium.org, mhocko@kernel.org, labbott@redhat.com, jglisse@redhat.com, hch@infradead.org, cl@linux.com, linux-security-module@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com On Sun, Feb 11, 2018 at 05:19:15AM +0200, 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. > Examples: > * 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, > to track their beginning. > > For details, see the documentation inside lib/genalloc.c > > Signed-off-by: Igor Stoppa > --- > include/linux/genalloc.h | 4 +- > lib/genalloc.c | 527 ++++++++++++++++++++++++++++++++++------------- > 2 files changed, 390 insertions(+), 141 deletions(-) > > diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h > index 872f930f1b06..dcaa33e74b1c 100644 > --- a/include/linux/genalloc.h > +++ b/include/linux/genalloc.h > @@ -32,7 +32,7 @@ > > #include > #include > -#include > +#include > > struct device; > struct device_node; > @@ -76,7 +76,7 @@ struct gen_pool_chunk { > phys_addr_t phys_addr; /* physical starting address of memory chunk */ > unsigned long start_addr; /* start address of memory chunk */ > unsigned long end_addr; /* end address of memory chunk (inclusive) */ > - unsigned long bits[0]; /* bitmap for allocating memory chunk */ > + unsigned long entries[0]; /* bitmap for allocating memory chunk */ > }; > > /* > diff --git a/lib/genalloc.c b/lib/genalloc.c > index ca06adc4f445..044347163acb 100644 > --- a/lib/genalloc.c > +++ b/lib/genalloc.c > @@ -26,6 +26,74 @@ > * > * This source code is licensed under the GNU General Public License, > * Version 2. See the file COPYING for more details. > + * > + * > + * > + * Encoding of the bitmap tracking the allocations > + * ----------------------------------------------- > + * > + * The bitmap is composed of units of allocations. > + * > + * Each unit of allocation is represented using 2 consecutive bits. > + * > + * This makes it possible to encode, for each unit of allocation, > + * information about: > + * - allocation status (busy/free) > + * - beginning of a sequennce of allocation units (first / successive) > + * > + * > + * Dictionary of allocation units (msb to the left, lsb to the right): > + * > + * 11: first allocation unit in the allocation > + * 10: any subsequent allocation unit (if any) in the allocation > + * 00: available allocation unit > + * 01: invalid > + * > + * Example, using 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 > + * > + * The encoding allows for lockless operations, such as: > + * - search for a sufficiently large range of allocation units > + * - reservation of a selected range of allocation units > + * - release of a specific allocation > + * > + * The alignment at which to perform the research for sequence of empty > + * allocation units (marked as zeros in the bitmap) is 2^1. > + * > + * This means that an allocation can start only at even places > + * (bit 0, bit 2, etc.) in the bitmap. > + * > + * Therefore, the number of zeroes to look for must be twice the number > + * of desired allocation units. > + * > + * 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 can be either set to 0, for automated > + * assessment, or it can be specified explicitly. > + * > + * In case it is specified explicitly, the value is verified agaisnt what > + * the library is tracking internally. > + * > + * If ever needed, the bitmap could be extended, assigning larger amounts > + * of bits to each allocation unit (the increase must follow powers of 2), > + * to track other properties of the allocations. > */ > > #include > @@ -36,118 +104,230 @@ > #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 > + * > + * Return: 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 Documentation/doc-guide/kernel-doc.rst recommends to to include brackets for function comments. I haven't noticed any difference in the resulting html, so I'm not sure if the brackets are actually required. > + * @size: amount in bytes > + * @order: power of 2 represented by each entry in the bitmap > + * > + * Returns the number of units representing the size. Please s/Return/Return:/ > + */ > +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, in bytes > + * @chunk: pointer to the struct describing the chunk > + * > + * Return: The size of the chunk, in bytes. > + */ > 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 > + * > + * Return: 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) > + > +/** > + * clear_bits_ll - according to the mask, clears 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 clear > + * > + * Return: 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 users > - * 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. > + * Return: 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 with an allocation > + * @alteration: indicates if the bits selected should be set or cleared > * @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 > + * > + * The modification happens lock-lessly. > + * Several users can write to the same map simultaneously, without lock. > * > - * 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. > + * Return: If two users alter the same bit, to one it will return > + * remaining entries, to the other it will return 0. And what if there are three or four concurrent users? ;-) I believe that a more elaborate description about what happens with concurrent attempts to alter the bitmap would be really helpful. > */ > -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. > + */ > + 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); > + > + /* > + * 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. > + */ > + 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 > * memory not managed by the regular kmalloc/kfree interface. > + * > + * Return: pointer to the pool, if successful, NULL otherwise > */ > struct gen_pool *gen_pool_create(int min_alloc_order, int nid) > { > @@ -177,16 +357,18 @@ EXPORT_SYMBOL(gen_pool_create); > * > * Add a new chunk of special memory to the specified pool. > * > - * Returns 0 on success or a -ve errno on failure. > + * Return: 0 on success or a -ve errno on failure. > */ > int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phys, > 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; > @@ -209,7 +391,7 @@ EXPORT_SYMBOL(gen_pool_add_virt); > * @pool: pool to allocate from > * @addr: starting address of memory > * > - * Returns the physical address on success, or -1 on error. > + * Return: the physical address on success, or -1 on error. > */ > phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr) > { > @@ -248,7 +430,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); > @@ -267,6 +449,8 @@ EXPORT_SYMBOL(gen_pool_destroy); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size) > { > @@ -285,6 +469,8 @@ EXPORT_SYMBOL(gen_pool_alloc); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size, > genpool_algo_t algo, void *data) > @@ -292,7 +478,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 +487,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; > } > @@ -342,6 +531,8 @@ EXPORT_SYMBOL(gen_pool_alloc_algo); > * Uses the pool allocation function (with first-fit algorithm by default). > * Can not be used in NMI handler on architectures without > * NMI-safe cmpxchg implementation. > + * > + * Return: address of the memory allocated, otherwise NULL > */ > void *gen_pool_dma_alloc(struct gen_pool *pool, size_t size, dma_addr_t *dma) > { > @@ -365,7 +556,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 +566,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; > } > @@ -428,8 +626,9 @@ EXPORT_SYMBOL(gen_pool_for_each_chunk); > * @start: start address > * @size: size of the region > * > - * Check if the range of addresses falls within the specified pool. Returns > - * true if the entire range is contained in the pool and false otherwise. > + * Check if the range of addresses falls within the specified pool. > + * > + * Return: true if the entire range is contained in the pool, false otherwise. > */ > bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > size_t size) > @@ -455,7 +654,7 @@ bool addr_in_gen_pool(struct gen_pool *pool, unsigned long start, > * gen_pool_avail - get available free space of the pool > * @pool: pool to get available free space > * > - * Return available free space of the specified pool. > + * Return: available free space of the specified pool. > */ > size_t gen_pool_avail(struct gen_pool *pool) > { > @@ -474,7 +673,7 @@ EXPORT_SYMBOL_GPL(gen_pool_avail); > * gen_pool_size - get size in bytes of memory managed by the pool > * @pool: pool to get size > * > - * Return size in bytes of memory managed by the pool. > + * Return: size in bytes of memory managed by the pool. > */ > size_t gen_pool_size(struct gen_pool *pool) > { > @@ -517,17 +716,27 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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,11 +744,13 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -547,23 +758,32 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > @@ -571,20 +791,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,60 +816,84 @@ 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 > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > 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); > > /** > * gen_pool_best_fit - find the best fitting region of memory > - * macthing the size requirement (no alignment constraint) > + * 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 > * > * Iterate over the bitmap to find the smallest free region > * which we can allocate the memory. > + * > + * Return: index of the memory allocated, otherwise the end of the range > */ > unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size, > unsigned long start, unsigned int nr, void *data, > struct gen_pool *pool) > { > - unsigned long start_bit = size; > + unsigned long start_bit = ENTRIES_TO_BITS(size); > unsigned long len = size + 1; > unsigned long index; > + unsigned long align_mask; > + unsigned long bit_index; > > - index = bitmap_find_next_zero_area(map, size, start, nr, 0); > + 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); > + index = BITS_DIV_ENTRIES(bit_index); > > while (index < size) { > - int next_bit = find_next_bit(map, size, index + nr); > - if ((next_bit - index) < len) { > - len = next_bit - index; > - start_bit = index; > + int next_bit; > + > + next_bit = find_next_bit(map, ENTRIES_TO_BITS(size), > + ENTRIES_TO_BITS(index + nr)); > + if ((BITS_DIV_ENTRIES(next_bit) - index) < len) { > + len = BITS_DIV_ENTRIES(next_bit) - index; > + start_bit = ENTRIES_TO_BITS(index); > if (len == nr) > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > - index = bitmap_find_next_zero_area(map, size, > - next_bit + 1, nr, 0); > + bit_index = > + bitmap_find_next_zero_area(map, > + ENTRIES_TO_BITS(size), > + next_bit + 1, > + ENTRIES_TO_BITS(nr), > + align_mask); > + index = BITS_DIV_ENTRIES(bit_index); > } > > - return start_bit; > + return BITS_DIV_ENTRIES(start_bit); > } > -EXPORT_SYMBOL(gen_pool_best_fit); > > static void devm_gen_pool_release(struct device *dev, void *res) > { > @@ -672,7 +919,7 @@ static int devm_gen_pool_match(struct device *dev, void *res, void *data) > * @dev: device to retrieve the gen_pool from > * @name: name of a gen_pool or NULL, identifies a particular gen_pool on device > * > - * Returns the gen_pool for the device if one is present, or NULL. > + * Return: the gen_pool for the device if one is present, or NULL. > */ > struct gen_pool *gen_pool_get(struct device *dev, const char *name) > { > @@ -696,6 +943,8 @@ EXPORT_SYMBOL_GPL(gen_pool_get); > * Create a new special memory pool that can be used to manage special purpose > * memory not managed by the regular kmalloc/kfree interface. The pool will be > * automatically destroyed by the device management code. > + * > + * Return: the address of the pool, if successful, otherwise NULL > */ > struct gen_pool *devm_gen_pool_create(struct device *dev, int min_alloc_order, > int nid, const char *name) > @@ -743,7 +992,7 @@ EXPORT_SYMBOL(devm_gen_pool_create); > * @propname: property name containing phandle(s) > * @index: index into the phandle array > * > - * Returns the pool that contains the chunk starting at the physical > + * Return: the pool that contains the chunk starting at the physical > * address of the device tree node pointed at by the phandle property, > * or NULL if not found. > */ > -- > 2.14.1 > > -- > 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 > > -- Sincerely yours, Mike. -- 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