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