^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) * Implementation of the extensible bitmap type.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Author : Stephen Smalley, <sds@tycho.nsa.gov>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * Updated: Hewlett-Packard <paul@paul-moore.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * Added support to import/export the NetLabel category bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * Applied standard bit operations to improve bitmap scanning.
^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) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include <linux/errno.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) #include <linux/jhash.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) #include <net/netlabel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #include "ebitmap.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) #include "policydb.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #define BITS_PER_U64 (sizeof(u64) * 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) static struct kmem_cache *ebitmap_node_cachep;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) struct ebitmap_node *n1, *n2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) if (e1->highbit != e2->highbit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) n1 = e1->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) n2 = e2->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) while (n1 && n2 &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) (n1->startbit == n2->startbit) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) n1 = n1->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) n2 = n2->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) if (n1 || n2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) struct ebitmap_node *n, *new, *prev;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) ebitmap_init(dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) n = src->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) prev = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) while (n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) if (!new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) ebitmap_destroy(dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) new->startbit = n->startbit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) new->next = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) if (prev)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) prev->next = new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) dst->node = new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) prev = new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) n = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) dst->highbit = src->highbit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) int ebitmap_and(struct ebitmap *dst, struct ebitmap *e1, struct ebitmap *e2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) struct ebitmap_node *n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) int bit, rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) ebitmap_init(dst);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) ebitmap_for_each_positive_bit(e1, n, bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) if (ebitmap_get_bit(e2, bit)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) rc = ebitmap_set_bit(dst, bit, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) if (rc < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) #ifdef CONFIG_NETLABEL
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * @ebmap: the ebitmap to export
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * @catmap: the NetLabel category bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * Description:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * Returns zero on success, negative values on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) int ebitmap_netlbl_export(struct ebitmap *ebmap,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) struct netlbl_lsm_catmap **catmap)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) struct ebitmap_node *e_iter = ebmap->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) unsigned long e_map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) u32 offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) unsigned int iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) int rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) if (e_iter == NULL) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) *catmap = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) if (*catmap != NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) netlbl_catmap_free(*catmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) *catmap = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) while (e_iter) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) offset = e_iter->startbit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) for (iter = 0; iter < EBITMAP_UNIT_NUMS; iter++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) e_map = e_iter->maps[iter];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) if (e_map != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) rc = netlbl_catmap_setlong(catmap,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) offset,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) e_map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) GFP_ATOMIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) if (rc != 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) goto netlbl_export_failure;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) offset += EBITMAP_UNIT_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) e_iter = e_iter->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) netlbl_export_failure:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) netlbl_catmap_free(*catmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) * @ebmap: the ebitmap to import
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) * @catmap: the NetLabel category bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) * Description:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) * Returns zero on success, negative values on error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) int ebitmap_netlbl_import(struct ebitmap *ebmap,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) struct netlbl_lsm_catmap *catmap)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) int rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) struct ebitmap_node *e_iter = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) struct ebitmap_node *e_prev = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) u32 offset = 0, idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) unsigned long bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) rc = netlbl_catmap_getlong(catmap, &offset, &bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) if (rc < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) goto netlbl_import_failure;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) if (offset == (u32)-1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) /* don't waste ebitmap space if the netlabel bitmap is empty */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) if (bitmap == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) offset += EBITMAP_UNIT_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) if (e_iter == NULL ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) offset >= e_iter->startbit + EBITMAP_SIZE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) e_prev = e_iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) e_iter = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) if (e_iter == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) goto netlbl_import_failure;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) e_iter->startbit = offset - (offset % EBITMAP_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) if (e_prev == NULL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) ebmap->node = e_iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) e_prev->next = e_iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) /* offset will always be aligned to an unsigned long */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) idx = EBITMAP_NODE_INDEX(e_iter, offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) e_iter->maps[idx] = bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) /* next */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) offset += EBITMAP_UNIT_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) /* NOTE: we should never reach this return */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) netlbl_import_failure:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) ebitmap_destroy(ebmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) #endif /* CONFIG_NETLABEL */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) * Check to see if all the bits set in e2 are also set in e1. Optionally,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) * last_e2bit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) struct ebitmap_node *n1, *n2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) if (e1->highbit < e2->highbit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) n1 = e1->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) n2 = e2->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) while (n1 && n2 && (n1->startbit <= n2->startbit)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) if (n1->startbit < n2->startbit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) n1 = n1->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) i--; /* Skip trailing NULL map entries */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) if (last_e2bit && (i >= 0)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) __fls(n2->maps[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) if (lastsetbit > last_e2bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) while (i >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) i--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) n1 = n1->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) n2 = n2->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) if (n2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) struct ebitmap_node *n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) if (e->highbit < bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) n = e->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) while (n && (n->startbit <= bit)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) if ((n->startbit + EBITMAP_SIZE) > bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) return ebitmap_node_get_bit(n, bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) n = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) struct ebitmap_node *n, *prev, *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) prev = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) n = e->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) while (n && n->startbit <= bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) if ((n->startbit + EBITMAP_SIZE) > bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) if (value) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) ebitmap_node_set_bit(n, bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) unsigned int s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) ebitmap_node_clr_bit(n, bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) s = find_first_bit(n->maps, EBITMAP_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) if (s < EBITMAP_SIZE)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) /* drop this node from the bitmap */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) if (!n->next) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) * this was the highest map
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) * within the bitmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) if (prev)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) e->highbit = prev->startbit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) + EBITMAP_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) e->highbit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) if (prev)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) prev->next = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) e->node = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) kmem_cache_free(ebitmap_node_cachep, n);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) prev = n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) n = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) if (!value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) if (!new)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) new->startbit = bit - (bit % EBITMAP_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) ebitmap_node_set_bit(new, bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) if (!n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) /* this node will be the highest map within the bitmap */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) e->highbit = new->startbit + EBITMAP_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) if (prev) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) new->next = prev->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) prev->next = new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) new->next = e->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) e->node = new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) void ebitmap_destroy(struct ebitmap *e)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) struct ebitmap_node *n, *temp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) if (!e)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) n = e->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) while (n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) temp = n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) n = n->next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) kmem_cache_free(ebitmap_node_cachep, temp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) e->highbit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) e->node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) int ebitmap_read(struct ebitmap *e, void *fp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) struct ebitmap_node *n = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) u32 mapunit, count, startbit, index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) __le32 ebitmap_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) u64 map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) __le64 mapbits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) __le32 buf[3];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) int rc, i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) ebitmap_init(e);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) rc = next_entry(buf, fp, sizeof buf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) if (rc < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) mapunit = le32_to_cpu(buf[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) e->highbit = le32_to_cpu(buf[1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) count = le32_to_cpu(buf[2]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) if (mapunit != BITS_PER_U64) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) pr_err("SELinux: ebitmap: map size %u does not "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) "match my size %zd (high bit was %d)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) mapunit, BITS_PER_U64, e->highbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) /* round up e->highbit */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) e->highbit += EBITMAP_SIZE - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) e->highbit -= (e->highbit % EBITMAP_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) if (!e->highbit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) e->node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) goto ok;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) if (e->highbit && !count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) for (i = 0; i < count; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) rc = next_entry(&ebitmap_start, fp, sizeof(u32));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) if (rc < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) pr_err("SELinux: ebitmap: truncated map\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) startbit = le32_to_cpu(ebitmap_start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) if (startbit & (mapunit - 1)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) pr_err("SELinux: ebitmap start bit (%d) is "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) "not a multiple of the map unit size (%u)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) startbit, mapunit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) if (startbit > e->highbit - mapunit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) pr_err("SELinux: ebitmap start bit (%d) is "
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) "beyond the end of the bitmap (%u)\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) startbit, (e->highbit - mapunit));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) struct ebitmap_node *tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) tmp = kmem_cache_zalloc(ebitmap_node_cachep, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) if (!tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) pr_err("SELinux: ebitmap: out of memory\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) rc = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) /* round down */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) if (n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) n->next = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) e->node = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) n = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) } else if (startbit <= n->startbit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) pr_err("SELinux: ebitmap: start bit %d"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) " comes after start bit %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) startbit, n->startbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) rc = next_entry(&mapbits, fp, sizeof(u64));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) if (rc < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) pr_err("SELinux: ebitmap: truncated map\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) goto bad;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) map = le64_to_cpu(mapbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) while (map) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) n->maps[index++] = map & (-1UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) map = EBITMAP_SHIFT_UNIT_SIZE(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) ok:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) rc = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) bad:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) if (!rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) rc = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) ebitmap_destroy(e);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) int ebitmap_write(struct ebitmap *e, void *fp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) struct ebitmap_node *n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) u32 count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) __le32 buf[3];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) u64 map;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) int bit, last_bit, last_startbit, rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) buf[0] = cpu_to_le32(BITS_PER_U64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) last_bit = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) last_startbit = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) ebitmap_for_each_positive_bit(e, n, bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) last_startbit = rounddown(bit, BITS_PER_U64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) last_bit = roundup(bit + 1, BITS_PER_U64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) buf[1] = cpu_to_le32(last_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) buf[2] = cpu_to_le32(count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) rc = put_entry(buf, sizeof(u32), 3, fp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) if (rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) map = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) last_startbit = INT_MIN;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) ebitmap_for_each_positive_bit(e, n, bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) __le64 buf64[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) /* this is the very first bit */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) if (!map) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) last_startbit = rounddown(bit, BITS_PER_U64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) map = (u64)1 << (bit - last_startbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) /* write the last node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) buf[0] = cpu_to_le32(last_startbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) rc = put_entry(buf, sizeof(u32), 1, fp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) if (rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) buf64[0] = cpu_to_le64(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) rc = put_entry(buf64, sizeof(u64), 1, fp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) if (rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) /* set up for the next node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) map = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) last_startbit = rounddown(bit, BITS_PER_U64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) map |= (u64)1 << (bit - last_startbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) /* write the last node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) if (map) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) __le64 buf64[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) /* write the last node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) buf[0] = cpu_to_le32(last_startbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) rc = put_entry(buf, sizeof(u32), 1, fp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) if (rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) buf64[0] = cpu_to_le64(map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) rc = put_entry(buf64, sizeof(u64), 1, fp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) if (rc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) u32 ebitmap_hash(const struct ebitmap *e, u32 hash)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) struct ebitmap_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) /* need to change hash even if ebitmap is empty */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) hash = jhash_1word(e->highbit, hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) for (node = e->node; node; node = node->next) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) hash = jhash_1word(node->startbit, hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) hash = jhash(node->maps, sizeof(node->maps), hash);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) return hash;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) void __init ebitmap_cache_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) ebitmap_node_cachep = kmem_cache_create("ebitmap_node",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) sizeof(struct ebitmap_node),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) 0, SLAB_PANIC, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags