Back to home page

LXR

 
 

    


0001 /*
0002  * Flexible array managed in PAGE_SIZE parts
0003  *
0004  * This program is free software; you can redistribute it and/or modify
0005  * it under the terms of the GNU General Public License as published by
0006  * the Free Software Foundation; either version 2 of the License, or
0007  * (at your option) any later version.
0008  *
0009  * This program is distributed in the hope that it will be useful,
0010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012  * GNU General Public License for more details.
0013  *
0014  * You should have received a copy of the GNU General Public License
0015  * along with this program; if not, write to the Free Software
0016  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
0017  *
0018  * Copyright IBM Corporation, 2009
0019  *
0020  * Author: Dave Hansen <dave@linux.vnet.ibm.com>
0021  */
0022 
0023 #include <linux/flex_array.h>
0024 #include <linux/slab.h>
0025 #include <linux/stddef.h>
0026 #include <linux/export.h>
0027 #include <linux/reciprocal_div.h>
0028 
0029 struct flex_array_part {
0030     char elements[FLEX_ARRAY_PART_SIZE];
0031 };
0032 
0033 /*
0034  * If a user requests an allocation which is small
0035  * enough, we may simply use the space in the
0036  * flex_array->parts[] array to store the user
0037  * data.
0038  */
0039 static inline int elements_fit_in_base(struct flex_array *fa)
0040 {
0041     int data_size = fa->element_size * fa->total_nr_elements;
0042     if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
0043         return 1;
0044     return 0;
0045 }
0046 
0047 /**
0048  * flex_array_alloc - allocate a new flexible array
0049  * @element_size:   the size of individual elements in the array
0050  * @total:      total number of elements that this should hold
0051  * @flags:      page allocation flags to use for base array
0052  *
0053  * Note: all locking must be provided by the caller.
0054  *
0055  * @total is used to size internal structures.  If the user ever
0056  * accesses any array indexes >=@total, it will produce errors.
0057  *
0058  * The maximum number of elements is defined as: the number of
0059  * elements that can be stored in a page times the number of
0060  * page pointers that we can fit in the base structure or (using
0061  * integer math):
0062  *
0063  *  (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
0064  *
0065  * Here's a table showing example capacities.  Note that the maximum
0066  * index that the get/put() functions is just nr_objects-1.   This
0067  * basically means that you get 4MB of storage on 32-bit and 2MB on
0068  * 64-bit.
0069  *
0070  *
0071  * Element size | Objects | Objects |
0072  * PAGE_SIZE=4k |  32-bit |  64-bit |
0073  * ---------------------------------|
0074  *      1 bytes | 4177920 | 2088960 |
0075  *      2 bytes | 2088960 | 1044480 |
0076  *      3 bytes | 1392300 |  696150 |
0077  *      4 bytes | 1044480 |  522240 |
0078  *     32 bytes |  130560 |   65408 |
0079  *     33 bytes |  126480 |   63240 |
0080  *   2048 bytes |    2040 |    1020 |
0081  *   2049 bytes |    1020 |     510 |
0082  *       void * | 1044480 |  261120 |
0083  *
0084  * Since 64-bit pointers are twice the size, we lose half the
0085  * capacity in the base structure.  Also note that no effort is made
0086  * to efficiently pack objects across page boundaries.
0087  */
0088 struct flex_array *flex_array_alloc(int element_size, unsigned int total,
0089                     gfp_t flags)
0090 {
0091     struct flex_array *ret;
0092     int elems_per_part = 0;
0093     int max_size = 0;
0094     struct reciprocal_value reciprocal_elems = { 0 };
0095 
0096     if (element_size) {
0097         elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
0098         reciprocal_elems = reciprocal_value(elems_per_part);
0099         max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
0100     }
0101 
0102     /* max_size will end up 0 if element_size > PAGE_SIZE */
0103     if (total > max_size)
0104         return NULL;
0105     ret = kzalloc(sizeof(struct flex_array), flags);
0106     if (!ret)
0107         return NULL;
0108     ret->element_size = element_size;
0109     ret->total_nr_elements = total;
0110     ret->elems_per_part = elems_per_part;
0111     ret->reciprocal_elems = reciprocal_elems;
0112     if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
0113         memset(&ret->parts[0], FLEX_ARRAY_FREE,
0114                         FLEX_ARRAY_BASE_BYTES_LEFT);
0115     return ret;
0116 }
0117 EXPORT_SYMBOL(flex_array_alloc);
0118 
0119 static int fa_element_to_part_nr(struct flex_array *fa,
0120                     unsigned int element_nr)
0121 {
0122     /*
0123      * if element_size == 0 we don't get here, so we never touch
0124      * the zeroed fa->reciprocal_elems, which would yield invalid
0125      * results
0126      */
0127     return reciprocal_divide(element_nr, fa->reciprocal_elems);
0128 }
0129 
0130 /**
0131  * flex_array_free_parts - just free the second-level pages
0132  * @fa:     the flex array from which to free parts
0133  *
0134  * This is to be used in cases where the base 'struct flex_array'
0135  * has been statically allocated and should not be free.
0136  */
0137 void flex_array_free_parts(struct flex_array *fa)
0138 {
0139     int part_nr;
0140 
0141     if (elements_fit_in_base(fa))
0142         return;
0143     for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
0144         kfree(fa->parts[part_nr]);
0145 }
0146 EXPORT_SYMBOL(flex_array_free_parts);
0147 
0148 void flex_array_free(struct flex_array *fa)
0149 {
0150     flex_array_free_parts(fa);
0151     kfree(fa);
0152 }
0153 EXPORT_SYMBOL(flex_array_free);
0154 
0155 static unsigned int index_inside_part(struct flex_array *fa,
0156                     unsigned int element_nr,
0157                     unsigned int part_nr)
0158 {
0159     unsigned int part_offset;
0160 
0161     part_offset = element_nr - part_nr * fa->elems_per_part;
0162     return part_offset * fa->element_size;
0163 }
0164 
0165 static struct flex_array_part *
0166 __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
0167 {
0168     struct flex_array_part *part = fa->parts[part_nr];
0169     if (!part) {
0170         part = kmalloc(sizeof(struct flex_array_part), flags);
0171         if (!part)
0172             return NULL;
0173         if (!(flags & __GFP_ZERO))
0174             memset(part, FLEX_ARRAY_FREE,
0175                 sizeof(struct flex_array_part));
0176         fa->parts[part_nr] = part;
0177     }
0178     return part;
0179 }
0180 
0181 /**
0182  * flex_array_put - copy data into the array at @element_nr
0183  * @fa:     the flex array to copy data into
0184  * @element_nr: index of the position in which to insert
0185  *      the new element.
0186  * @src:    address of data to copy into the array
0187  * @flags:  page allocation flags to use for array expansion
0188  *
0189  *
0190  * Note that this *copies* the contents of @src into
0191  * the array.  If you are trying to store an array of
0192  * pointers, make sure to pass in &ptr instead of ptr.
0193  * You may instead wish to use the flex_array_put_ptr()
0194  * helper function.
0195  *
0196  * Locking must be provided by the caller.
0197  */
0198 int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
0199             gfp_t flags)
0200 {
0201     int part_nr = 0;
0202     struct flex_array_part *part;
0203     void *dst;
0204 
0205     if (element_nr >= fa->total_nr_elements)
0206         return -ENOSPC;
0207     if (!fa->element_size)
0208         return 0;
0209     if (elements_fit_in_base(fa))
0210         part = (struct flex_array_part *)&fa->parts[0];
0211     else {
0212         part_nr = fa_element_to_part_nr(fa, element_nr);
0213         part = __fa_get_part(fa, part_nr, flags);
0214         if (!part)
0215             return -ENOMEM;
0216     }
0217     dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
0218     memcpy(dst, src, fa->element_size);
0219     return 0;
0220 }
0221 EXPORT_SYMBOL(flex_array_put);
0222 
0223 /**
0224  * flex_array_clear - clear element in array at @element_nr
0225  * @fa:     the flex array of the element.
0226  * @element_nr: index of the position to clear.
0227  *
0228  * Locking must be provided by the caller.
0229  */
0230 int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
0231 {
0232     int part_nr = 0;
0233     struct flex_array_part *part;
0234     void *dst;
0235 
0236     if (element_nr >= fa->total_nr_elements)
0237         return -ENOSPC;
0238     if (!fa->element_size)
0239         return 0;
0240     if (elements_fit_in_base(fa))
0241         part = (struct flex_array_part *)&fa->parts[0];
0242     else {
0243         part_nr = fa_element_to_part_nr(fa, element_nr);
0244         part = fa->parts[part_nr];
0245         if (!part)
0246             return -EINVAL;
0247     }
0248     dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
0249     memset(dst, FLEX_ARRAY_FREE, fa->element_size);
0250     return 0;
0251 }
0252 EXPORT_SYMBOL(flex_array_clear);
0253 
0254 /**
0255  * flex_array_prealloc - guarantee that array space exists
0256  * @fa:         the flex array for which to preallocate parts
0257  * @start:      index of first array element for which space is allocated
0258  * @nr_elements:    number of elements for which space is allocated
0259  * @flags:      page allocation flags
0260  *
0261  * This will guarantee that no future calls to flex_array_put()
0262  * will allocate memory.  It can be used if you are expecting to
0263  * be holding a lock or in some atomic context while writing
0264  * data into the array.
0265  *
0266  * Locking must be provided by the caller.
0267  */
0268 int flex_array_prealloc(struct flex_array *fa, unsigned int start,
0269             unsigned int nr_elements, gfp_t flags)
0270 {
0271     int start_part;
0272     int end_part;
0273     int part_nr;
0274     unsigned int end;
0275     struct flex_array_part *part;
0276 
0277     if (!start && !nr_elements)
0278         return 0;
0279     if (start >= fa->total_nr_elements)
0280         return -ENOSPC;
0281     if (!nr_elements)
0282         return 0;
0283 
0284     end = start + nr_elements - 1;
0285 
0286     if (end >= fa->total_nr_elements)
0287         return -ENOSPC;
0288     if (!fa->element_size)
0289         return 0;
0290     if (elements_fit_in_base(fa))
0291         return 0;
0292     start_part = fa_element_to_part_nr(fa, start);
0293     end_part = fa_element_to_part_nr(fa, end);
0294     for (part_nr = start_part; part_nr <= end_part; part_nr++) {
0295         part = __fa_get_part(fa, part_nr, flags);
0296         if (!part)
0297             return -ENOMEM;
0298     }
0299     return 0;
0300 }
0301 EXPORT_SYMBOL(flex_array_prealloc);
0302 
0303 /**
0304  * flex_array_get - pull data back out of the array
0305  * @fa:     the flex array from which to extract data
0306  * @element_nr: index of the element to fetch from the array
0307  *
0308  * Returns a pointer to the data at index @element_nr.  Note
0309  * that this is a copy of the data that was passed in.  If you
0310  * are using this to store pointers, you'll get back &ptr.  You
0311  * may instead wish to use the flex_array_get_ptr helper.
0312  *
0313  * Locking must be provided by the caller.
0314  */
0315 void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
0316 {
0317     int part_nr = 0;
0318     struct flex_array_part *part;
0319 
0320     if (!fa->element_size)
0321         return NULL;
0322     if (element_nr >= fa->total_nr_elements)
0323         return NULL;
0324     if (elements_fit_in_base(fa))
0325         part = (struct flex_array_part *)&fa->parts[0];
0326     else {
0327         part_nr = fa_element_to_part_nr(fa, element_nr);
0328         part = fa->parts[part_nr];
0329         if (!part)
0330             return NULL;
0331     }
0332     return &part->elements[index_inside_part(fa, element_nr, part_nr)];
0333 }
0334 EXPORT_SYMBOL(flex_array_get);
0335 
0336 /**
0337  * flex_array_get_ptr - pull a ptr back out of the array
0338  * @fa:     the flex array from which to extract data
0339  * @element_nr: index of the element to fetch from the array
0340  *
0341  * Returns the pointer placed in the flex array at element_nr using
0342  * flex_array_put_ptr().  This function should not be called if the
0343  * element in question was not set using the _put_ptr() helper.
0344  */
0345 void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr)
0346 {
0347     void **tmp;
0348 
0349     tmp = flex_array_get(fa, element_nr);
0350     if (!tmp)
0351         return NULL;
0352 
0353     return *tmp;
0354 }
0355 EXPORT_SYMBOL(flex_array_get_ptr);
0356 
0357 static int part_is_free(struct flex_array_part *part)
0358 {
0359     int i;
0360 
0361     for (i = 0; i < sizeof(struct flex_array_part); i++)
0362         if (part->elements[i] != FLEX_ARRAY_FREE)
0363             return 0;
0364     return 1;
0365 }
0366 
0367 /**
0368  * flex_array_shrink - free unused second-level pages
0369  * @fa:     the flex array to shrink
0370  *
0371  * Frees all second-level pages that consist solely of unused
0372  * elements.  Returns the number of pages freed.
0373  *
0374  * Locking must be provided by the caller.
0375  */
0376 int flex_array_shrink(struct flex_array *fa)
0377 {
0378     struct flex_array_part *part;
0379     int part_nr;
0380     int ret = 0;
0381 
0382     if (!fa->total_nr_elements || !fa->element_size)
0383         return 0;
0384     if (elements_fit_in_base(fa))
0385         return ret;
0386     for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
0387         part = fa->parts[part_nr];
0388         if (!part)
0389             continue;
0390         if (part_is_free(part)) {
0391             fa->parts[part_nr] = NULL;
0392             kfree(part);
0393             ret++;
0394         }
0395     }
0396     return ret;
0397 }
0398 EXPORT_SYMBOL(flex_array_shrink);