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