Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0
       2                 :            : /*
       3                 :            :  * Implementation of the extensible bitmap type.
       4                 :            :  *
       5                 :            :  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
       6                 :            :  */
       7                 :            : /*
       8                 :            :  * Updated: Hewlett-Packard <paul@paul-moore.com>
       9                 :            :  *
      10                 :            :  *      Added support to import/export the NetLabel category bitmap
      11                 :            :  *
      12                 :            :  * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
      13                 :            :  */
      14                 :            : /*
      15                 :            :  * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
      16                 :            :  *      Applied standard bit operations to improve bitmap scanning.
      17                 :            :  */
      18                 :            : 
      19                 :            : #include <linux/kernel.h>
      20                 :            : #include <linux/slab.h>
      21                 :            : #include <linux/errno.h>
      22                 :            : #include <net/netlabel.h>
      23                 :            : #include "ebitmap.h"
      24                 :            : #include "policydb.h"
      25                 :            : 
      26                 :            : #define BITS_PER_U64    (sizeof(u64) * 8)
      27                 :            : 
      28                 :            : static struct kmem_cache *ebitmap_node_cachep;
      29                 :            : 
      30                 :          0 : int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
      31                 :            : {
      32                 :          0 :         struct ebitmap_node *n1, *n2;
      33                 :            : 
      34         [ #  # ]:          0 :         if (e1->highbit != e2->highbit)
      35                 :            :                 return 0;
      36                 :            : 
      37                 :          0 :         n1 = e1->node;
      38                 :          0 :         n2 = e2->node;
      39         [ #  # ]:          0 :         while (n1 && n2 &&
      40         [ #  # ]:          0 :                (n1->startbit == n2->startbit) &&
      41         [ #  # ]:          0 :                !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
      42                 :          0 :                 n1 = n1->next;
      43                 :          0 :                 n2 = n2->next;
      44                 :            :         }
      45                 :            : 
      46         [ #  # ]:          0 :         if (n1 || n2)
      47                 :          0 :                 return 0;
      48                 :            : 
      49                 :            :         return 1;
      50                 :            : }
      51                 :            : 
      52                 :          0 : int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
      53                 :            : {
      54                 :          0 :         struct ebitmap_node *n, *new, *prev;
      55                 :            : 
      56                 :          0 :         ebitmap_init(dst);
      57                 :          0 :         n = src->node;
      58                 :          0 :         prev = NULL;
      59         [ #  # ]:          0 :         while (n) {
      60                 :          0 :                 new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
      61         [ #  # ]:          0 :                 if (!new) {
      62                 :          0 :                         ebitmap_destroy(dst);
      63                 :          0 :                         return -ENOMEM;
      64                 :            :                 }
      65                 :          0 :                 new->startbit = n->startbit;
      66                 :          0 :                 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
      67                 :          0 :                 new->next = NULL;
      68         [ #  # ]:          0 :                 if (prev)
      69                 :          0 :                         prev->next = new;
      70                 :            :                 else
      71                 :          0 :                         dst->node = new;
      72                 :          0 :                 prev = new;
      73                 :          0 :                 n = n->next;
      74                 :            :         }
      75                 :            : 
      76                 :          0 :         dst->highbit = src->highbit;
      77                 :          0 :         return 0;
      78                 :            : }
      79                 :            : 
      80                 :          0 : int ebitmap_and(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2)
      81                 :            : {
      82                 :          0 :         struct ebitmap_node *n;
      83                 :          0 :         int bit, rc;
      84                 :            : 
      85                 :          0 :         ebitmap_init(dst);
      86                 :            : 
      87         [ #  # ]:          0 :         ebitmap_for_each_positive_bit(e1, n, bit) {
      88         [ #  # ]:          0 :                 if (ebitmap_get_bit(e2, bit)) {
      89                 :          0 :                         rc = ebitmap_set_bit(dst, bit, 1);
      90         [ #  # ]:          0 :                         if (rc < 0)
      91                 :          0 :                                 return rc;
      92                 :            :                 }
      93                 :            :         }
      94                 :            :         return 0;
      95                 :            : }
      96                 :            : 
      97                 :            : 
      98                 :            : #ifdef CONFIG_NETLABEL
      99                 :            : /**
     100                 :            :  * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
     101                 :            :  * @ebmap: the ebitmap to export
     102                 :            :  * @catmap: the NetLabel category bitmap
     103                 :            :  *
     104                 :            :  * Description:
     105                 :            :  * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
     106                 :            :  * Returns zero on success, negative values on error.
     107                 :            :  *
     108                 :            :  */
     109                 :          0 : int ebitmap_netlbl_export(struct ebitmap *ebmap,
     110                 :            :                           struct netlbl_lsm_catmap **catmap)
     111                 :            : {
     112                 :          0 :         struct ebitmap_node *e_iter = ebmap->node;
     113                 :          0 :         unsigned long e_map;
     114                 :          0 :         u32 offset;
     115                 :          0 :         unsigned int iter;
     116                 :          0 :         int rc;
     117                 :            : 
     118         [ #  # ]:          0 :         if (e_iter == NULL) {
     119                 :          0 :                 *catmap = NULL;
     120                 :          0 :                 return 0;
     121                 :            :         }
     122                 :            : 
     123         [ #  # ]:          0 :         if (*catmap != NULL)
     124                 :            :                 netlbl_catmap_free(*catmap);
     125                 :          0 :         *catmap = NULL;
     126                 :            : 
     127         [ #  # ]:          0 :         while (e_iter) {
     128                 :          0 :                 offset = e_iter->startbit;
     129         [ #  # ]:          0 :                 for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) {
     130                 :          0 :                         e_map = e_iter->maps[iter];
     131         [ #  # ]:          0 :                         if (e_map != 0) {
     132                 :          0 :                                 rc = netlbl_catmap_setlong(catmap,
     133                 :            :                                                            offset,
     134                 :            :                                                            e_map,
     135                 :            :                                                            GFP_ATOMIC);
     136         [ #  # ]:          0 :                                 if (rc != 0)
     137                 :          0 :                                         goto netlbl_export_failure;
     138                 :            :                         }
     139                 :          0 :                         offset += EBITMAP_UNIT_SIZE;
     140                 :            :                 }
     141                 :          0 :                 e_iter = e_iter->next;
     142                 :            :         }
     143                 :            : 
     144                 :            :         return 0;
     145                 :            : 
     146                 :            : netlbl_export_failure:
     147                 :          0 :         netlbl_catmap_free(*catmap);
     148                 :            :         return -ENOMEM;
     149                 :            : }
     150                 :            : 
     151                 :            : /**
     152                 :            :  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
     153                 :            :  * @ebmap: the ebitmap to import
     154                 :            :  * @catmap: the NetLabel category bitmap
     155                 :            :  *
     156                 :            :  * Description:
     157                 :            :  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
     158                 :            :  * Returns zero on success, negative values on error.
     159                 :            :  *
     160                 :            :  */
     161                 :          0 : int ebitmap_netlbl_import(struct ebitmap *ebmap,
     162                 :            :                           struct netlbl_lsm_catmap *catmap)
     163                 :            : {
     164                 :          0 :         int rc;
     165                 :          0 :         struct ebitmap_node *e_iter = NULL;
     166                 :          0 :         struct ebitmap_node *e_prev = NULL;
     167                 :          0 :         u32 offset = 0, idx;
     168                 :          0 :         unsigned long bitmap;
     169                 :            : 
     170                 :          0 :         for (;;) {
     171                 :          0 :                 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap);
     172         [ #  # ]:          0 :                 if (rc < 0)
     173                 :          0 :                         goto netlbl_import_failure;
     174         [ #  # ]:          0 :                 if (offset == (u32)-1)
     175                 :            :                         return 0;
     176                 :            : 
     177                 :            :                 /* don't waste ebitmap space if the netlabel bitmap is empty */
     178         [ #  # ]:          0 :                 if (bitmap == 0) {
     179                 :          0 :                         offset += EBITMAP_UNIT_SIZE;
     180                 :          0 :                         continue;
     181                 :            :                 }
     182                 :            : 
     183         [ #  # ]:          0 :                 if (e_iter == NULL ||
     184         [ #  # ]:          0 :                     offset >= e_iter->startbit + EBITMAP_SIZE) {
     185                 :          0 :                         e_prev = e_iter;
     186                 :          0 :                         e_iter = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
     187         [ #  # ]:          0 :                         if (e_iter == NULL)
     188                 :          0 :                                 goto netlbl_import_failure;
     189                 :          0 :                         e_iter->startbit = offset - (offset % EBITMAP_SIZE);
     190         [ #  # ]:          0 :                         if (e_prev == NULL)
     191                 :          0 :                                 ebmap->node = e_iter;
     192                 :            :                         else
     193                 :          0 :                                 e_prev->next = e_iter;
     194                 :          0 :                         ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
     195                 :            :                 }
     196                 :            : 
     197                 :            :                 /* offset will always be aligned to an unsigned long */
     198                 :          0 :                 idx = EBITMAP_NODE_INDEX(e_iter, offset);
     199                 :          0 :                 e_iter->maps[idx] = bitmap;
     200                 :            : 
     201                 :            :                 /* next */
     202                 :          0 :                 offset += EBITMAP_UNIT_SIZE;
     203                 :            :         }
     204                 :            : 
     205                 :            :         /* NOTE: we should never reach this return */
     206                 :            :         return 0;
     207                 :            : 
     208                 :          0 : netlbl_import_failure:
     209                 :          0 :         ebitmap_destroy(ebmap);
     210                 :          0 :         return -ENOMEM;
     211                 :            : }
     212                 :            : #endif /* CONFIG_NETLABEL */
     213                 :            : 
     214                 :            : /*
     215                 :            :  * Check to see if all the bits set in e2 are also set in e1. Optionally,
     216                 :            :  * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
     217                 :            :  * last_e2bit.
     218                 :            :  */
     219                 :          0 : int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
     220                 :            : {
     221                 :          0 :         struct ebitmap_node *n1, *n2;
     222                 :          0 :         int i;
     223                 :            : 
     224         [ #  # ]:          0 :         if (e1->highbit < e2->highbit)
     225                 :            :                 return 0;
     226                 :            : 
     227                 :          0 :         n1 = e1->node;
     228                 :          0 :         n2 = e2->node;
     229                 :            : 
     230   [ #  #  #  # ]:          0 :         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
     231         [ #  # ]:          0 :                 if (n1->startbit < n2->startbit) {
     232                 :          0 :                         n1 = n1->next;
     233                 :          0 :                         continue;
     234                 :            :                 }
     235   [ #  #  #  # ]:          0 :                 for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
     236                 :          0 :                         i--;    /* Skip trailing NULL map entries */
     237         [ #  # ]:          0 :                 if (last_e2bit && (i >= 0)) {
     238                 :          0 :                         u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
     239         [ #  # ]:          0 :                                          __fls(n2->maps[i]);
     240         [ #  # ]:          0 :                         if (lastsetbit > last_e2bit)
     241                 :            :                                 return 0;
     242                 :            :                 }
     243                 :            : 
     244         [ #  # ]:          0 :                 while (i >= 0) {
     245         [ #  # ]:          0 :                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
     246                 :            :                                 return 0;
     247                 :          0 :                         i--;
     248                 :            :                 }
     249                 :            : 
     250                 :          0 :                 n1 = n1->next;
     251                 :          0 :                 n2 = n2->next;
     252                 :            :         }
     253                 :            : 
     254         [ #  # ]:          0 :         if (n2)
     255                 :          0 :                 return 0;
     256                 :            : 
     257                 :            :         return 1;
     258                 :            : }
     259                 :            : 
     260                 :          0 : int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
     261                 :            : {
     262                 :          0 :         struct ebitmap_node *n;
     263                 :            : 
     264         [ #  # ]:          0 :         if (e->highbit < bit)
     265                 :            :                 return 0;
     266                 :            : 
     267                 :          0 :         n = e->node;
     268   [ #  #  #  # ]:          0 :         while (n && (n->startbit <= bit)) {
     269         [ #  # ]:          0 :                 if ((n->startbit + EBITMAP_SIZE) > bit)
     270         [ #  # ]:          0 :                         return ebitmap_node_get_bit(n, bit);
     271                 :          0 :                 n = n->next;
     272                 :            :         }
     273                 :            : 
     274                 :            :         return 0;
     275                 :            : }
     276                 :            : 
     277                 :          0 : int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
     278                 :            : {
     279                 :          0 :         struct ebitmap_node *n, *prev, *new;
     280                 :            : 
     281                 :          0 :         prev = NULL;
     282                 :          0 :         n = e->node;
     283   [ #  #  #  # ]:          0 :         while (n && n->startbit <= bit) {
     284         [ #  # ]:          0 :                 if ((n->startbit + EBITMAP_SIZE) > bit) {
     285         [ #  # ]:          0 :                         if (value) {
     286         [ #  # ]:          0 :                                 ebitmap_node_set_bit(n, bit);
     287                 :            :                         } else {
     288                 :          0 :                                 unsigned int s;
     289                 :            : 
     290         [ #  # ]:          0 :                                 ebitmap_node_clr_bit(n, bit);
     291                 :            : 
     292                 :          0 :                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
     293         [ #  # ]:          0 :                                 if (s < EBITMAP_SIZE)
     294                 :            :                                         return 0;
     295                 :            : 
     296                 :            :                                 /* drop this node from the bitmap */
     297         [ #  # ]:          0 :                                 if (!n->next) {
     298                 :            :                                         /*
     299                 :            :                                          * this was the highest map
     300                 :            :                                          * within the bitmap
     301                 :            :                                          */
     302         [ #  # ]:          0 :                                         if (prev)
     303                 :          0 :                                                 e->highbit = prev->startbit
     304                 :          0 :                                                              + EBITMAP_SIZE;
     305                 :            :                                         else
     306                 :          0 :                                                 e->highbit = 0;
     307                 :            :                                 }
     308         [ #  # ]:          0 :                                 if (prev)
     309                 :          0 :                                         prev->next = n->next;
     310                 :            :                                 else
     311                 :          0 :                                         e->node = n->next;
     312                 :          0 :                                 kmem_cache_free(ebitmap_node_cachep, n);
     313                 :            :                         }
     314                 :          0 :                         return 0;
     315                 :            :                 }
     316                 :          0 :                 prev = n;
     317                 :          0 :                 n = n->next;
     318                 :            :         }
     319                 :            : 
     320         [ #  # ]:          0 :         if (!value)
     321                 :            :                 return 0;
     322                 :            : 
     323                 :          0 :         new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
     324         [ #  # ]:          0 :         if (!new)
     325                 :            :                 return -ENOMEM;
     326                 :            : 
     327                 :          0 :         new->startbit = bit - (bit % EBITMAP_SIZE);
     328         [ #  # ]:          0 :         ebitmap_node_set_bit(new, bit);
     329                 :            : 
     330         [ #  # ]:          0 :         if (!n)
     331                 :            :                 /* this node will be the highest map within the bitmap */
     332                 :          0 :                 e->highbit = new->startbit + EBITMAP_SIZE;
     333                 :            : 
     334         [ #  # ]:          0 :         if (prev) {
     335                 :          0 :                 new->next = prev->next;
     336                 :          0 :                 prev->next = new;
     337                 :            :         } else {
     338                 :          0 :                 new->next = e->node;
     339                 :          0 :                 e->node = new;
     340                 :            :         }
     341                 :            : 
     342                 :            :         return 0;
     343                 :            : }
     344                 :            : 
     345                 :          0 : void ebitmap_destroy(struct ebitmap *e)
     346                 :            : {
     347                 :          0 :         struct ebitmap_node *n, *temp;
     348                 :            : 
     349         [ #  # ]:          0 :         if (!e)
     350                 :            :                 return;
     351                 :            : 
     352                 :          0 :         n = e->node;
     353         [ #  # ]:          0 :         while (n) {
     354                 :          0 :                 temp = n;
     355                 :          0 :                 n = n->next;
     356                 :          0 :                 kmem_cache_free(ebitmap_node_cachep, temp);
     357                 :            :         }
     358                 :            : 
     359                 :          0 :         e->highbit = 0;
     360                 :          0 :         e->node = NULL;
     361                 :          0 :         return;
     362                 :            : }
     363                 :            : 
     364                 :          0 : int ebitmap_read(struct ebitmap *e, void *fp)
     365                 :            : {
     366                 :          0 :         struct ebitmap_node *n = NULL;
     367                 :          0 :         u32 mapunit, count, startbit, index;
     368                 :          0 :         __le32 ebitmap_start;
     369                 :          0 :         u64 map;
     370                 :          0 :         __le64 mapbits;
     371                 :          0 :         __le32 buf[3];
     372                 :          0 :         int rc, i;
     373                 :            : 
     374         [ #  # ]:          0 :         ebitmap_init(e);
     375                 :            : 
     376         [ #  # ]:          0 :         rc = next_entry(buf, fp, sizeof buf);
     377                 :          0 :         if (rc < 0)
     378                 :          0 :                 goto out;
     379                 :            : 
     380                 :          0 :         mapunit = le32_to_cpu(buf[0]);
     381                 :          0 :         e->highbit = le32_to_cpu(buf[1]);
     382                 :          0 :         count = le32_to_cpu(buf[2]);
     383                 :            : 
     384         [ #  # ]:          0 :         if (mapunit != BITS_PER_U64) {
     385                 :          0 :                 pr_err("SELinux: ebitmap: map size %u does not "
     386                 :            :                        "match my size %zd (high bit was %d)\n",
     387                 :            :                        mapunit, BITS_PER_U64, e->highbit);
     388                 :          0 :                 goto bad;
     389                 :            :         }
     390                 :            : 
     391                 :            :         /* round up e->highbit */
     392                 :          0 :         e->highbit += EBITMAP_SIZE - 1;
     393                 :          0 :         e->highbit -= (e->highbit % EBITMAP_SIZE);
     394                 :            : 
     395         [ #  # ]:          0 :         if (!e->highbit) {
     396                 :          0 :                 e->node = NULL;
     397                 :          0 :                 goto ok;
     398                 :            :         }
     399                 :            : 
     400         [ #  # ]:          0 :         if (e->highbit && !count)
     401                 :          0 :                 goto bad;
     402                 :            : 
     403         [ #  # ]:          0 :         for (i = 0; i < count; i++) {
     404         [ #  # ]:          0 :                 rc = next_entry(&ebitmap_start, fp, sizeof(u32));
     405                 :          0 :                 if (rc < 0) {
     406                 :          0 :                         pr_err("SELinux: ebitmap: truncated map\n");
     407                 :          0 :                         goto bad;
     408                 :            :                 }
     409                 :          0 :                 startbit = le32_to_cpu(ebitmap_start);
     410                 :            : 
     411         [ #  # ]:          0 :                 if (startbit & (mapunit - 1)) {
     412                 :          0 :                         pr_err("SELinux: ebitmap start bit (%d) is "
     413                 :            :                                "not a multiple of the map unit size (%u)\n",
     414                 :            :                                startbit, mapunit);
     415                 :          0 :                         goto bad;
     416                 :            :                 }
     417         [ #  # ]:          0 :                 if (startbit > e->highbit - mapunit) {
     418                 :          0 :                         pr_err("SELinux: ebitmap start bit (%d) is "
     419                 :            :                                "beyond the end of the bitmap (%u)\n",
     420                 :            :                                startbit, (e->highbit - mapunit));
     421                 :          0 :                         goto bad;
     422                 :            :                 }
     423                 :            : 
     424   [ #  #  #  # ]:          0 :                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
     425                 :          0 :                         struct ebitmap_node *tmp;
     426                 :          0 :                         tmp = kmem_cache_zalloc(ebitmap_node_cachep, GFP_KERNEL);
     427         [ #  # ]:          0 :                         if (!tmp) {
     428                 :          0 :                                 pr_err("SELinux: ebitmap: out of memory\n");
     429                 :          0 :                                 rc = -ENOMEM;
     430                 :          0 :                                 goto bad;
     431                 :            :                         }
     432                 :            :                         /* round down */
     433                 :          0 :                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
     434         [ #  # ]:          0 :                         if (n)
     435                 :          0 :                                 n->next = tmp;
     436                 :            :                         else
     437                 :          0 :                                 e->node = tmp;
     438                 :            :                         n = tmp;
     439         [ #  # ]:          0 :                 } else if (startbit <= n->startbit) {
     440                 :          0 :                         pr_err("SELinux: ebitmap: start bit %d"
     441                 :            :                                " comes after start bit %d\n",
     442                 :            :                                startbit, n->startbit);
     443                 :          0 :                         goto bad;
     444                 :            :                 }
     445                 :            : 
     446         [ #  # ]:          0 :                 rc = next_entry(&mapbits, fp, sizeof(u64));
     447                 :          0 :                 if (rc < 0) {
     448                 :          0 :                         pr_err("SELinux: ebitmap: truncated map\n");
     449                 :          0 :                         goto bad;
     450                 :            :                 }
     451                 :          0 :                 map = le64_to_cpu(mapbits);
     452                 :            : 
     453                 :          0 :                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
     454         [ #  # ]:          0 :                 while (map) {
     455                 :          0 :                         n->maps[index++] = map & (-1UL);
     456                 :          0 :                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
     457                 :            :                 }
     458                 :            :         }
     459                 :          0 : ok:
     460                 :            :         rc = 0;
     461                 :          0 : out:
     462                 :          0 :         return rc;
     463                 :          0 : bad:
     464         [ #  # ]:          0 :         if (!rc)
     465                 :          0 :                 rc = -EINVAL;
     466                 :          0 :         ebitmap_destroy(e);
     467                 :          0 :         goto out;
     468                 :            : }
     469                 :            : 
     470                 :          0 : int ebitmap_write(struct ebitmap *e, void *fp)
     471                 :            : {
     472                 :          0 :         struct ebitmap_node *n;
     473                 :          0 :         u32 count;
     474                 :          0 :         __le32 buf[3];
     475                 :          0 :         u64 map;
     476                 :          0 :         int bit, last_bit, last_startbit, rc;
     477                 :            : 
     478                 :          0 :         buf[0] = cpu_to_le32(BITS_PER_U64);
     479                 :            : 
     480                 :          0 :         count = 0;
     481                 :          0 :         last_bit = 0;
     482                 :          0 :         last_startbit = -1;
     483         [ #  # ]:          0 :         ebitmap_for_each_positive_bit(e, n, bit) {
     484         [ #  # ]:          0 :                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
     485                 :          0 :                         count++;
     486                 :          0 :                         last_startbit = rounddown(bit, BITS_PER_U64);
     487                 :            :                 }
     488                 :          0 :                 last_bit = roundup(bit + 1, BITS_PER_U64);
     489                 :            :         }
     490                 :          0 :         buf[1] = cpu_to_le32(last_bit);
     491                 :          0 :         buf[2] = cpu_to_le32(count);
     492                 :            : 
     493                 :          0 :         rc = put_entry(buf, sizeof(u32), 3, fp);
     494                 :          0 :         if (rc)
     495                 :            :                 return rc;
     496                 :            : 
     497                 :          0 :         map = 0;
     498                 :          0 :         last_startbit = INT_MIN;
     499         [ #  # ]:          0 :         ebitmap_for_each_positive_bit(e, n, bit) {
     500         [ #  # ]:          0 :                 if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
     501                 :          0 :                         __le64 buf64[1];
     502                 :            : 
     503                 :            :                         /* this is the very first bit */
     504         [ #  # ]:          0 :                         if (!map) {
     505                 :          0 :                                 last_startbit = rounddown(bit, BITS_PER_U64);
     506                 :          0 :                                 map = (u64)1 << (bit - last_startbit);
     507                 :          0 :                                 continue;
     508                 :            :                         }
     509                 :            : 
     510                 :            :                         /* write the last node */
     511                 :          0 :                         buf[0] = cpu_to_le32(last_startbit);
     512                 :          0 :                         rc = put_entry(buf, sizeof(u32), 1, fp);
     513                 :          0 :                         if (rc)
     514                 :            :                                 return rc;
     515                 :            : 
     516                 :          0 :                         buf64[0] = cpu_to_le64(map);
     517                 :          0 :                         rc = put_entry(buf64, sizeof(u64), 1, fp);
     518                 :          0 :                         if (rc)
     519                 :            :                                 return rc;
     520                 :            : 
     521                 :            :                         /* set up for the next node */
     522                 :          0 :                         map = 0;
     523                 :          0 :                         last_startbit = rounddown(bit, BITS_PER_U64);
     524                 :            :                 }
     525                 :          0 :                 map |= (u64)1 << (bit - last_startbit);
     526                 :            :         }
     527                 :            :         /* write the last node */
     528         [ #  # ]:          0 :         if (map) {
     529                 :          0 :                 __le64 buf64[1];
     530                 :            : 
     531                 :            :                 /* write the last node */
     532                 :          0 :                 buf[0] = cpu_to_le32(last_startbit);
     533                 :          0 :                 rc = put_entry(buf, sizeof(u32), 1, fp);
     534                 :          0 :                 if (rc)
     535                 :            :                         return rc;
     536                 :            : 
     537                 :          0 :                 buf64[0] = cpu_to_le64(map);
     538                 :          0 :                 rc = put_entry(buf64, sizeof(u64), 1, fp);
     539                 :          0 :                 if (rc)
     540                 :            :                         return rc;
     541                 :            :         }
     542                 :          0 :         return 0;
     543                 :            : }
     544                 :            : 
     545                 :         13 : void __init ebitmap_cache_init(void)
     546                 :            : {
     547                 :         13 :         ebitmap_node_cachep = kmem_cache_create("ebitmap_node",
     548                 :            :                                                         sizeof(struct ebitmap_node),
     549                 :            :                                                         0, SLAB_PANIC, NULL);
     550                 :         13 : }