src/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_types.h"
  39 #include "ext4_misc.h"
  40 #include "ext4_errno.h"
  41 #include "ext4_debug.h"
  42
  43 #include "ext4_bitmap.h"
  44
  45 void ext4_bmap_bits_free(uint8_t *bmap, uint32_t sbit, uint32_t bcnt)
  46 {
  47         uint32_t i = sbit;
  48
  49         while (i & 7) {
  50
  51                 if (!bcnt)
  52                         return;
  53
  54                 ext4_bmap_bit_clr(bmap, i);
  55
  56                 bcnt--;
  57                 i++;
  58         }
  59         sbit = i;
  60         bmap += (sbit >> 3);
  61
  62 #if CONFIG_UNALIGNED_ACCESS
  63         while (bcnt >= 32) {
  64                 *(uint32_t *)bmap = 0;
  65                 bmap += 4;
  66                 bcnt -= 32;
  67                 sbit += 32;
  68         }
  69
  70         while (bcnt >= 16) {
  71                 *(uint16_t *)bmap = 0;
  72                 bmap += 2;
  73                 bcnt -= 16;
  74                 sbit += 16;
  75         }
  76 #endif
  77
  78         while (bcnt >= 8) {
  79                 *bmap = 0;
  80                 bmap += 1;
  81                 bcnt -= 8;
  82                 sbit += 8;
  83         }
  84
  85         for (i = 0; i < bcnt; ++i) {
  86                 ext4_bmap_bit_clr(bmap, i);
  87         }
  88 }
  89
  90 int ext4_bmap_bit_find_clr(uint8_t *bmap, uint32_t sbit, uint32_t ebit,
  91                            uint32_t *bit_id)
  92 {
  93         uint32_t i;
  94         uint32_t bcnt = ebit - sbit;
  95
  96         i = sbit;
  97
  98         while (i & 7) {
  99
 100                 if (!bcnt)
 101                         return ENOSPC;
 102
 103                 if (ext4_bmap_is_bit_clr(bmap, i)) {
 104                         *bit_id = sbit;
 105                         return EOK;
 106                 }
 107
 108                 i++;
 109                 bcnt--;
 110         }
 111
 112         sbit = i;
 113         bmap += (sbit >> 3);
 114
 115 #if CONFIG_UNALIGNED_ACCESS
 116         while (bcnt >= 32) {
 117                 if (*(uint32_t *)bmap != 0xFFFFFFFF)
 118                         goto finish_it;
 119
 120                 bmap += 4;
 121                 bcnt -= 32;
 122                 sbit += 32;
 123         }
 124
 125         while (bcnt >= 16) {
 126                 if (*(uint16_t *)bmap != 0xFFFF)
 127                         goto finish_it;
 128
 129                 bmap += 2;
 130                 bcnt -= 16;
 131                 sbit += 16;
 132         }
 133 finish_it:
 134 #endif
 135         while (bcnt >= 8) {
 136                 if (*bmap != 0xFF) {
 137                         for (i = 0; i < 8; ++i) {
 138                                 if (ext4_bmap_is_bit_clr(bmap, i)) {
 139                                         *bit_id = sbit + i;
 140                                         return EOK;
 141                                 }
 142                         }
 143                 }
 144
 145                 bmap += 1;
 146                 bcnt -= 8;
 147                 sbit += 8;
 148         }
 149
 150         for (i = 0; i < bcnt; ++i) {
 151                 if (ext4_bmap_is_bit_clr(bmap, i)) {
 152                         *bit_id = sbit + i;
 153                         return EOK;
 154                 }
 155         }
 156
 157         return ENOSPC;
 158 }
 159
 160 /**
 161  * @}
 162  */