osfmk/tests/bitmap_test.c

   1 /*
   2  * Copyright (c) 2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29
  30 #if DEVELOPMENT || DEBUG
  31
  32 #include <tests/xnupost.h>
  33 #include <kern/kalloc.h>
  34 #include <kern/bits.h>
  35 #include <pexpert/pexpert.h>
  36
  37 extern void dump_bitmap_next(bitmap_t *map, uint nbits);
  38 extern void dump_bitmap_lsb(bitmap_t *map, uint nbits);
  39 extern void test_bitmap(void);
  40 extern kern_return_t bitmap_post_test(void);
  41
  42 void
  43 dump_bitmap_next(bitmap_t *map, uint nbits)
  44 {
  45         for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
  46                 printf(" %d", i);
  47         }
  48         printf("\n");
  49 }
  50
  51 void
  52 dump_bitmap_lsb(bitmap_t *map, uint nbits)
  53 {
  54         for (int i = bitmap_lsb_first(map, nbits); i >= 0; i = bitmap_lsb_next(map, nbits, i)) {
  55                 printf(" %d", i);
  56         }
  57         printf("\n");
  58 }
  59
  60 #ifdef NOTDEF
  61 #ifdef assert
  62 #undef assert
  63 #endif
  64 #define assert(x)       T_ASSERT(x, NULL)
  65 #endif
  66
  67 void
  68 test_bitmap(void)
  69 {
  70         uint start = 60;
  71         for (uint nbits = start; nbits <= 192; nbits++) {
  72                 bitmap_t *map = bitmap_alloc(nbits);
  73
  74                 for (uint i = 0; i < nbits; i++) {
  75                         bitmap_set(map, i);
  76                 }
  77                 assert(bitmap_is_full(map, nbits));
  78
  79                 int expected_result = nbits - 1;
  80                 for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
  81                         assert(i == expected_result);
  82                         expected_result--;
  83                 }
  84                 assert(expected_result == -1);
  85
  86                 bitmap_zero(map, nbits);
  87
  88                 assert(bitmap_first(map, nbits) == -1);
  89                 assert(bitmap_lsb_first(map, nbits) == -1);
  90
  91                 bitmap_full(map, nbits);
  92                 assert(bitmap_is_full(map, nbits));
  93
  94                 expected_result = nbits - 1;
  95                 for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
  96                         assert(i == expected_result);
  97                         expected_result--;
  98                 }
  99                 assert(expected_result == -1);
 100
 101                 expected_result = 0;
 102                 for (int i = bitmap_lsb_first(map, nbits); i >= 0; i = bitmap_lsb_next(map, nbits, i)) {
 103                         assert(i == expected_result);
 104                         expected_result++;
 105                 }
 106                 assert(expected_result == (int)nbits);
 107
 108                 for (uint i = 0; i < nbits; i++) {
 109                         bitmap_clear(map, i);
 110                         assert(!bitmap_is_full(map, nbits));
 111                         bitmap_set(map, i);
 112                         assert(bitmap_is_full(map, nbits));
 113                 }
 114
 115                 for (uint i = 0; i < nbits; i++) {
 116                         bitmap_clear(map, i);
 117                 }
 118                 assert(bitmap_first(map, nbits) == -1);
 119                 assert(bitmap_lsb_first(map, nbits) == -1);
 120
 121                 /* bitmap_not */
 122                 bitmap_not(map, map, nbits);
 123                 assert(bitmap_is_full(map, nbits));
 124
 125                 bitmap_not(map, map, nbits);
 126                 assert(bitmap_first(map, nbits) == -1);
 127                 assert(bitmap_lsb_first(map, nbits) == -1);
 128
 129                 /* bitmap_and */
 130                 bitmap_t *map0 = bitmap_alloc(nbits);
 131                 assert(bitmap_first(map0, nbits) == -1);
 132
 133                 bitmap_t *map1 = bitmap_alloc(nbits);
 134                 bitmap_full(map1, nbits);
 135                 assert(bitmap_is_full(map1, nbits));
 136
 137                 bitmap_and(map, map0, map1, nbits);
 138                 assert(bitmap_first(map, nbits) == -1);
 139
 140                 bitmap_and(map, map1, map1, nbits);
 141                 assert(bitmap_is_full(map, nbits));
 142
 143                 /* bitmap_and_not */
 144                 bitmap_and_not(map, map0, map1, nbits);
 145                 assert(bitmap_first(map, nbits) == -1);
 146
 147                 bitmap_and_not(map, map1, map0, nbits);
 148                 assert(bitmap_is_full(map, nbits));
 149
 150                 /* bitmap_equal */
 151                 for (uint i = 0; i < nbits; i++) {
 152                         bitmap_clear(map, i);
 153                         assert(!bitmap_equal(map, map1, nbits));
 154                         bitmap_set(map, i);
 155                         assert(bitmap_equal(map, map1, nbits));
 156                 }
 157
 158                 /* bitmap_and_not_mask_first */
 159                 for (uint i = 0; i < nbits; i++) {
 160                         bitmap_clear(map, i);
 161                         expected_result = i;
 162                         int result = bitmap_and_not_mask_first(map1, map, nbits);
 163                         assert(result == expected_result);
 164                         bitmap_set(map, i);
 165                         result = bitmap_and_not_mask_first(map1, map, nbits);
 166                         assert(result == -1);
 167                 }
 168
 169                 bitmap_free(map, nbits);
 170                 bitmap_free(map0, nbits);
 171                 bitmap_free(map1, nbits);
 172         }
 173 }
 174
 175 kern_return_t
 176 bitmap_post_test(void)
 177 {
 178         test_bitmap();
 179
 180         kern_return_t ret = KERN_SUCCESS;
 181
 182         T_ASSERT(ret == KERN_SUCCESS, NULL);
 183
 184         return ret;
 185 }
 186 #endif