bits.c 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182
  1. /*
  2. * Copyright (C) Sistina Software, Inc. 1997-2003 All rights reserved.
  3. * Copyright (C) 2004-2005 Red Hat, Inc. All rights reserved.
  4. *
  5. * This copyrighted material is made available to anyone wishing to use,
  6. * modify, copy, or redistribute it subject to the terms and conditions
  7. * of the GNU General Public License v.2.
  8. */
  9. /*
  10. * These routines are used by the resource group routines (rgrp.c)
  11. * to keep track of block allocation. Each block is represented by two
  12. * bits. One bit indicates whether or not the block is used. (1=used,
  13. * 0=free) The other bit indicates whether or not the block contains a
  14. * dinode or not. (1=dinode, 0=not-dinode) So, each byte represents
  15. * GFS2_NBBY (i.e. 4) blocks.
  16. */
  17. #include <linux/sched.h>
  18. #include <linux/slab.h>
  19. #include <linux/spinlock.h>
  20. #include <linux/completion.h>
  21. #include <linux/buffer_head.h>
  22. #include <linux/gfs2_ondisk.h>
  23. #include <asm/semaphore.h>
  24. #include "gfs2.h"
  25. #include "lm_interface.h"
  26. #include "incore.h"
  27. #include "bits.h"
  28. #include "util.h"
  29. static const char valid_change[16] = {
  30. /* current */
  31. /* n */ 0, 1, 0, 1,
  32. /* e */ 1, 0, 0, 0,
  33. /* w */ 0, 0, 0, 0,
  34. 1, 0, 0, 0
  35. };
  36. /**
  37. * gfs2_setbit - Set a bit in the bitmaps
  38. * @buffer: the buffer that holds the bitmaps
  39. * @buflen: the length (in bytes) of the buffer
  40. * @block: the block to set
  41. * @new_state: the new state of the block
  42. *
  43. */
  44. void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  45. unsigned int buflen, uint32_t block, unsigned char new_state)
  46. {
  47. unsigned char *byte, *end, cur_state;
  48. unsigned int bit;
  49. byte = buffer + (block / GFS2_NBBY);
  50. bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
  51. end = buffer + buflen;
  52. gfs2_assert(rgd->rd_sbd, byte < end);
  53. cur_state = (*byte >> bit) & GFS2_BIT_MASK;
  54. if (valid_change[new_state * 4 + cur_state]) {
  55. *byte ^= cur_state << bit;
  56. *byte |= new_state << bit;
  57. } else
  58. gfs2_consist_rgrpd(rgd);
  59. }
  60. /**
  61. * gfs2_testbit - test a bit in the bitmaps
  62. * @buffer: the buffer that holds the bitmaps
  63. * @buflen: the length (in bytes) of the buffer
  64. * @block: the block to read
  65. *
  66. */
  67. unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  68. unsigned int buflen, uint32_t block)
  69. {
  70. unsigned char *byte, *end, cur_state;
  71. unsigned int bit;
  72. byte = buffer + (block / GFS2_NBBY);
  73. bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
  74. end = buffer + buflen;
  75. gfs2_assert(rgd->rd_sbd, byte < end);
  76. cur_state = (*byte >> bit) & GFS2_BIT_MASK;
  77. return cur_state;
  78. }
  79. /**
  80. * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
  81. * a block in a given allocation state.
  82. * @buffer: the buffer that holds the bitmaps
  83. * @buflen: the length (in bytes) of the buffer
  84. * @goal: start search at this block's bit-pair (within @buffer)
  85. * @old_state: GFS2_BLKST_XXX the state of the block we're looking for;
  86. * bit 0 = alloc(1)/free(0), bit 1 = meta(1)/data(0)
  87. *
  88. * Scope of @goal and returned block number is only within this bitmap buffer,
  89. * not entire rgrp or filesystem. @buffer will be offset from the actual
  90. * beginning of a bitmap block buffer, skipping any header structures.
  91. *
  92. * Return: the block number (bitmap buffer scope) that was found
  93. */
  94. uint32_t gfs2_bitfit(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  95. unsigned int buflen, uint32_t goal,
  96. unsigned char old_state)
  97. {
  98. unsigned char *byte, *end, alloc;
  99. uint32_t blk = goal;
  100. unsigned int bit;
  101. byte = buffer + (goal / GFS2_NBBY);
  102. bit = (goal % GFS2_NBBY) * GFS2_BIT_SIZE;
  103. end = buffer + buflen;
  104. alloc = (old_state & 1) ? 0 : 0x55;
  105. while (byte < end) {
  106. if ((*byte & 0x55) == alloc) {
  107. blk += (8 - bit) >> 1;
  108. bit = 0;
  109. byte++;
  110. continue;
  111. }
  112. if (((*byte >> bit) & GFS2_BIT_MASK) == old_state)
  113. return blk;
  114. bit += GFS2_BIT_SIZE;
  115. if (bit >= 8) {
  116. bit = 0;
  117. byte++;
  118. }
  119. blk++;
  120. }
  121. return BFITNOENT;
  122. }
  123. /**
  124. * gfs2_bitcount - count the number of bits in a certain state
  125. * @buffer: the buffer that holds the bitmaps
  126. * @buflen: the length (in bytes) of the buffer
  127. * @state: the state of the block we're looking for
  128. *
  129. * Returns: The number of bits
  130. */
  131. uint32_t gfs2_bitcount(struct gfs2_rgrpd *rgd, unsigned char *buffer,
  132. unsigned int buflen, unsigned char state)
  133. {
  134. unsigned char *byte = buffer;
  135. unsigned char *end = buffer + buflen;
  136. unsigned char state1 = state << 2;
  137. unsigned char state2 = state << 4;
  138. unsigned char state3 = state << 6;
  139. uint32_t count = 0;
  140. for (; byte < end; byte++) {
  141. if (((*byte) & 0x03) == state)
  142. count++;
  143. if (((*byte) & 0x0C) == state1)
  144. count++;
  145. if (((*byte) & 0x30) == state2)
  146. count++;
  147. if (((*byte) & 0xC0) == state3)
  148. count++;
  149. }
  150. return count;
  151. }