Simplified distributed block storage with strong consistency, like in Ceph
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

163 lines
3.5 KiB

  1. // Copyright (c) Vitaliy Filippov, 2019+
  2. // License: VNPL-1.0 (see README.md for details)
  3. #include <stdexcept>
  4. #include "allocator.h"
  5. #include <stdlib.h>
  6. #include <malloc.h>
  7. allocator::allocator(uint64_t blocks)
  8. {
  9. if (blocks >= 0x80000000 || blocks <= 1)
  10. {
  11. throw std::invalid_argument("blocks");
  12. }
  13. uint64_t p2 = 1, total = 1;
  14. while (p2 * 64 < blocks)
  15. {
  16. p2 = p2 * 64;
  17. total += p2;
  18. }
  19. total -= p2;
  20. total += (blocks+63) / 64;
  21. mask = new uint64_t[2 + total];
  22. size = free = blocks;
  23. last_one_mask = (blocks % 64) == 0
  24. ? UINT64_MAX
  25. : ~(UINT64_MAX << (64 - blocks % 64));
  26. for (uint64_t i = 0; i < total; i++)
  27. {
  28. mask[i] = 0;
  29. }
  30. }
  31. allocator::~allocator()
  32. {
  33. delete[] mask;
  34. }
  35. void allocator::set(uint64_t addr, bool value)
  36. {
  37. if (addr >= size)
  38. {
  39. return;
  40. }
  41. uint64_t p2 = 1, offset = 0;
  42. while (p2 * 64 < size)
  43. {
  44. offset += p2;
  45. p2 = p2 * 64;
  46. }
  47. uint64_t cur_addr = addr;
  48. bool is_last = true;
  49. uint64_t value64 = value ? 1 : 0;
  50. while (1)
  51. {
  52. uint64_t last = offset + cur_addr/64;
  53. uint64_t bit = cur_addr % 64;
  54. if (((mask[last] >> bit) & 1) != value64)
  55. {
  56. if (is_last)
  57. {
  58. free += value ? -1 : 1;
  59. }
  60. if (value)
  61. {
  62. mask[last] = mask[last] | (1l << bit);
  63. if (mask[last] != (!is_last || cur_addr/64 < size/64
  64. ? UINT64_MAX : last_one_mask))
  65. {
  66. break;
  67. }
  68. }
  69. else
  70. {
  71. mask[last] = mask[last] & ~(1l << bit);
  72. }
  73. is_last = false;
  74. if (p2 > 1)
  75. {
  76. p2 = p2 / 64;
  77. offset -= p2;
  78. cur_addr /= 64;
  79. }
  80. else
  81. {
  82. break;
  83. }
  84. }
  85. else
  86. {
  87. break;
  88. }
  89. }
  90. }
  91. uint64_t allocator::find_free()
  92. {
  93. uint64_t p2 = 1, offset = 0, addr = 0, f, i;
  94. while (p2 < size)
  95. {
  96. uint64_t m = mask[offset + addr];
  97. for (i = 0, f = 1; i < 64; i++, f <<= 1)
  98. {
  99. if (!(m & f))
  100. {
  101. break;
  102. }
  103. }
  104. if (i == 64)
  105. {
  106. // No space
  107. return UINT64_MAX;
  108. }
  109. addr = (addr * 64) | i;
  110. if (addr >= size)
  111. {
  112. // No space
  113. return UINT64_MAX;
  114. }
  115. offset += p2;
  116. p2 = p2 * 64;
  117. }
  118. return addr;
  119. }
  120. uint64_t allocator::get_free_count()
  121. {
  122. return free;
  123. }
  124. void bitmap_set(void *bitmap, uint64_t start, uint64_t len, uint64_t bitmap_granularity)
  125. {
  126. if (start == 0)
  127. {
  128. if (len == 32*bitmap_granularity)
  129. {
  130. *((uint32_t*)bitmap) = UINT32_MAX;
  131. return;
  132. }
  133. else if (len == 64*bitmap_granularity)
  134. {
  135. *((uint64_t*)bitmap) = UINT64_MAX;
  136. return;
  137. }
  138. }
  139. unsigned bit_start = start / bitmap_granularity;
  140. unsigned bit_end = ((start + len) + bitmap_granularity - 1) / bitmap_granularity;
  141. while (bit_start < bit_end)
  142. {
  143. if (!(bit_start & 7) && bit_end >= bit_start+8)
  144. {
  145. ((uint8_t*)bitmap)[bit_start / 8] = UINT8_MAX;
  146. bit_start += 8;
  147. }
  148. else
  149. {
  150. ((uint8_t*)bitmap)[bit_start / 8] |= 1 << (bit_start % 8);
  151. bit_start++;
  152. }
  153. }
  154. }