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 27 static 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 34 static 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 41 static inline int 42 find_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 58 static inline int 59 find_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 91 static inline void 92 bitmap_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 100 static inline void 101 bitmap_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 109 static inline u_long 110 bitmap_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 132 static inline unsigned long 133 bitmap_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 } 138