jcs.org
jcs's openbsd hax
openbsd
1/* $OpenBSD: bitmap.h,v 1.1 2022/09/08 18:16:26 mglocker Exp $ */
2
3/*
4 * Copyright 2004 Eric Anholt
5 * All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the next
15 * paragraph) shall be included in all copies or substantial portions of the
16 * Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21 * VA LINUX SYSTEMS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 */
26
27static inline void
28__clear_bit(u_int b, volatile void *p)
29{
30 volatile u_int *ptr = (volatile u_int *)p;
31 ptr[b >> 5] &= ~(1 << (b & 0x1f));
32}
33
34static inline void
35__set_bit(u_int b, volatile void *p)
36{
37 volatile u_int *ptr = (volatile u_int *)p;
38 ptr[b >> 5] |= (1 << (b & 0x1f));
39}
40
41static inline int
42find_next_zero_bit(volatile void *p, int max, int b)
43{
44 volatile u_int *ptr = (volatile u_int *)p;
45
46 for (; b < max; b += 32) {
47 if (ptr[b >> 5] != ~0) {
48 for (;;) {
49 if ((ptr[b >> 5] & (1 << (b & 0x1f))) == 0)
50 return b;
51 b++;
52 }
53 }
54 }
55 return max;
56}
57
58static inline int
59find_next_bit(volatile void *p, int max, int b)
60{
61 volatile u_int *ptr = (volatile u_int *)p;
62
63 for (; b < max; b+= 32) {
64 if (ptr[b >> 5] != 0) {
65 for (;;) {
66 if (ptr[b >> 5] & (1 << (b & 0x1f)))
67 return b;
68 b++;
69 }
70 }
71 }
72 return max;
73}
74
75/*
76 * Copyright (c) 2013, 2014, 2015 Mark Kettenis
77 *
78 * Permission to use, copy, modify, and distribute this software for any
79 * purpose with or without fee is hereby granted, provided that the above
80 * copyright notice and this permission notice appear in all copies.
81 *
82 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
83 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
84 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
85 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
86 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
87 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
88 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
89 */
90
91static inline void
92bitmap_set(void *p, int b, u_int n)
93{
94 u_int end = b + n;
95
96 for (; b < end; b++)
97 __set_bit(b, p);
98}
99
100static inline void
101bitmap_clear(void *p, int b, u_int n)
102{
103 u_int end = b + n;
104
105 for (; b < end; b++)
106 __clear_bit(b, p);
107}
108
109static inline u_long
110bitmap_find_next_zero_area_off(void *p, u_long size, u_long start, u_long n,
111 u_long align_mask, u_long align_offset)
112{
113 u_long index, end, i;
114
115 while (1) {
116 index = (((find_next_zero_bit(p, size, start) +
117 align_offset) + align_mask) & ~align_mask) - align_offset;
118
119 end = index + n;
120 if (end > size)
121 return end;
122
123 i = find_next_bit(p, end, index);
124 if (i >= end)
125 break;
126 start = i + 1;
127 }
128
129 return index;
130}
131
132static inline unsigned long
133bitmap_find_next_zero_area(void *p, u_long size, u_long start, u_long n,
134 u_long align_mask)
135{
136 return bitmap_find_next_zero_area_off(p, size, start, n, align_mask, 0);
137}