lwext4/ext4_bitmap.c

   1 /*
   2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup lwext4
  30  * @{
  31  */
  32 /**
  33  * @file  ext4_bitmap.c
  34  * @brief Block/inode bitmap allocator.
  35  */
  36
  37 #include <ext4_config.h>
  38 #include <ext4_bitmap.h>
  39
  40 #include <ext4_errno.h>
  41
  42 void ext4_bmap_bits_free(uint8_t *bmap, uint32_t sbit, uint32_t bcnt)
  43 {
  44     uint32_t i = sbit;
  45
  46     while (i & 7) {
  47
  48         if (!bcnt)
  49             return;
  50
  51         ext4_bmap_bit_clr(bmap, i);
  52
  53         bcnt--;
  54         i++;
  55     }
  56     sbit = i;
  57     bmap += (sbit >> 3);
  58
  59     while (bcnt >= 32) {
  60         *(uint32_t *)bmap = 0;
  61         bmap += 4;
  62         bcnt -= 32;
  63         sbit += 32;
  64     }
  65
  66     while (bcnt >= 16) {
  67         *(uint16_t *)bmap = 0;
  68         bmap += 2;
  69         bcnt -= 16;
  70         sbit += 16;
  71     }
  72
  73     while (bcnt >= 8) {
  74         *bmap = 0;
  75         bmap += 1;
  76         bcnt -= 8;
  77         sbit += 8;
  78     }
  79
  80     for (i = 0; i < bcnt; ++i) {
  81         ext4_bmap_bit_clr(bmap, i);
  82     }
  83 }
  84
  85 int ext4_bmap_bit_find_clr(uint8_t *bmap, uint32_t sbit, uint32_t ebit,
  86                            uint32_t *bit_id)
  87 {
  88     uint32_t i;
  89     uint32_t bcnt = ebit - sbit;
  90
  91     i = sbit;
  92
  93     while (i & 7) {
  94
  95         if (!bcnt)
  96             return ENOSPC;
  97
  98         if (ext4_bmap_is_bit_clr(bmap, i)) {
  99             *bit_id = sbit;
 100             return EOK;
 101         }
 102
 103         i++;
 104         bcnt--;
 105     }
 106
 107     sbit = i;
 108     bmap += (sbit >> 3);
 109
 110     while (bcnt >= 32) {
 111         if (*(uint32_t *)bmap != 0xFFFFFFFF)
 112             goto finish_it;
 113
 114         bmap += 4;
 115         bcnt -= 32;
 116         sbit += 32;
 117     }
 118
 119     while (bcnt >= 16) {
 120         if (*(uint16_t *)bmap != 0xFFFF)
 121             goto finish_it;
 122
 123         bmap += 2;
 124         bcnt -= 16;
 125         sbit += 16;
 126     }
 127
 128 finish_it:
 129     while (bcnt >= 8) {
 130         if (*bmap != 0xFF) {
 131             for (i = 0; i < 8; ++i) {
 132                 if (ext4_bmap_is_bit_clr(bmap, i)) {
 133                     *bit_id = sbit + i;
 134                     return EOK;
 135                 }
 136             }
 137         }
 138
 139         bmap += 1;
 140         bcnt -= 8;
 141         sbit += 8;
 142     }
 143
 144     for (i = 0; i < bcnt; ++i) {
 145         if (ext4_bmap_is_bit_clr(bmap, i)) {
 146             *bit_id = sbit + i;
 147             return EOK;
 148         }
 149     }
 150
 151     return ENOSPC;
 152 }
 153
 154 /**
 155  * @}
 156  */