bitext.c 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * bitext.c: kernel little helper (of bit shuffling variety).
  4. *
  5. * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com>
  6. *
  7. * The algorithm to search a zero bit string is geared towards its application.
  8. * We expect a couple of fixed sizes of requests, so a rotating counter, reset
  9. * by align size, should provide fast enough search while maintaining low
  10. * fragmentation.
  11. */
  12. #include <linux/string.h>
  13. #include <linux/bitmap.h>
  14. #include <asm/bitext.h>
  15. /**
  16. * bit_map_string_get - find and set a bit string in bit map.
  17. * @t: the bit map.
  18. * @len: requested string length
  19. * @align: requested alignment
  20. *
  21. * Returns offset in the map or -1 if out of space.
  22. *
  23. * Not safe to call from an interrupt (uses spin_lock).
  24. */
  25. int bit_map_string_get(struct bit_map *t, int len, int align)
  26. {
  27. int offset, count; /* siamese twins */
  28. int off_new;
  29. int align1;
  30. int i, color;
  31. if (t->num_colors) {
  32. /* align is overloaded to be the page color */
  33. color = align;
  34. align = t->num_colors;
  35. } else {
  36. color = 0;
  37. if (align == 0)
  38. align = 1;
  39. }
  40. align1 = align - 1;
  41. if ((align & align1) != 0)
  42. BUG();
  43. if (align < 0 || align >= t->size)
  44. BUG();
  45. if (len <= 0 || len > t->size)
  46. BUG();
  47. color &= align1;
  48. spin_lock(&t->lock);
  49. if (len < t->last_size)
  50. offset = t->first_free;
  51. else
  52. offset = t->last_off & ~align1;
  53. count = 0;
  54. for (;;) {
  55. off_new = find_next_zero_bit(t->map, t->size, offset);
  56. off_new = ((off_new + align1) & ~align1) + color;
  57. count += off_new - offset;
  58. offset = off_new;
  59. if (offset >= t->size)
  60. offset = 0;
  61. if (count + len > t->size) {
  62. spin_unlock(&t->lock);
  63. /* P3 */ printk(KERN_ERR
  64. "bitmap out: size %d used %d off %d len %d align %d count %d\n",
  65. t->size, t->used, offset, len, align, count);
  66. return -1;
  67. }
  68. if (offset + len > t->size) {
  69. count += t->size - offset;
  70. offset = 0;
  71. continue;
  72. }
  73. i = 0;
  74. while (test_bit(offset + i, t->map) == 0) {
  75. i++;
  76. if (i == len) {
  77. bitmap_set(t->map, offset, len);
  78. if (offset == t->first_free)
  79. t->first_free = find_next_zero_bit
  80. (t->map, t->size,
  81. t->first_free + len);
  82. if ((t->last_off = offset + len) >= t->size)
  83. t->last_off = 0;
  84. t->used += len;
  85. t->last_size = len;
  86. spin_unlock(&t->lock);
  87. return offset;
  88. }
  89. }
  90. count += i + 1;
  91. if ((offset += i + 1) >= t->size)
  92. offset = 0;
  93. }
  94. }
  95. void bit_map_clear(struct bit_map *t, int offset, int len)
  96. {
  97. int i;
  98. if (t->used < len)
  99. BUG(); /* Much too late to do any good, but alas... */
  100. spin_lock(&t->lock);
  101. for (i = 0; i < len; i++) {
  102. if (test_bit(offset + i, t->map) == 0)
  103. BUG();
  104. __clear_bit(offset + i, t->map);
  105. }
  106. if (offset < t->first_free)
  107. t->first_free = offset;
  108. t->used -= len;
  109. spin_unlock(&t->lock);
  110. }
  111. void bit_map_init(struct bit_map *t, unsigned long *map, int size)
  112. {
  113. bitmap_zero(map, size);
  114. memset(t, 0, sizeof *t);
  115. spin_lock_init(&t->lock);
  116. t->map = map;
  117. t->size = size;
  118. }