1 /*
   2  * Copyright (c) 2018, Red Hat Inc. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 #include "precompiled.hpp"
  25 #include "utilities/bitMap.inline.hpp"
  26 #include "unittest.hpp"
  27 
  28 // Bitmap size should be large enough to accept large operations.
  29 static const BitMap::idx_t BITMAP_SIZE = 8192;
  30 
  31 // The test would like to fuzz indexes in this window. Having the fuzz
  32 // window at bitmap word size makes sure the test would touch every combination
  33 // of indexes (un)aligned on word boundary.
  34 static const BitMap::idx_t FUZZ_WINDOW = sizeof(BitMap::bm_word_t) * 8;
  35 
  36 static void verify_set(CHeapBitMap& map, BitMap::idx_t l, BitMap::idx_t r) {
  37   for (BitMap::idx_t c = l; c < r; c++) {
  38     EXPECT_TRUE(map.at(c));
  39   }
  40 }
  41 
  42 static void verify_unset(CHeapBitMap& map, BitMap::idx_t l, BitMap::idx_t r) {
  43   for (BitMap::idx_t c = l; c < r; c++) {
  44     EXPECT_FALSE(map.at(c));
  45   }
  46 }
  47 
  48 TEST(BitMap, clear_large_range) {
  49   CHeapBitMap map(BITMAP_SIZE);
  50 
  51   map.set_range(0, BITMAP_SIZE);
  52   verify_set(map, 0, BITMAP_SIZE);
  53 
  54   for (size_t size_class = 0; size_class <= BITMAP_SIZE; size_class = MAX2<size_t>(1, size_class*2)) {
  55     for (BitMap::idx_t l = 0; l < FUZZ_WINDOW; l++) {
  56       for (BitMap::idx_t tr = l; tr < FUZZ_WINDOW; tr++) {
  57         BitMap::idx_t r = MIN2(BITMAP_SIZE, size_class + tr); // avoid overflow
  58 
  59         map.clear_large_range(l, r);
  60         verify_unset(map, l, r);
  61         verify_set(map, 0, l);
  62         verify_set(map, r, BITMAP_SIZE);
  63 
  64         // Restore cleared
  65         map.set_range(l, r);
  66         verify_set(map, l, r);
  67       }
  68     }
  69   }
  70 }
  71 
  72 TEST(BitMap, set_large_range) {
  73   CHeapBitMap map(BITMAP_SIZE);
  74 
  75   map.clear();
  76   verify_unset(map, 0, BITMAP_SIZE);
  77 
  78   for (size_t size_class = 0; size_class <= BITMAP_SIZE; size_class = MAX2<size_t>(1, size_class*2)) {
  79     for (BitMap::idx_t l = 0; l < FUZZ_WINDOW; l++) {
  80       for (BitMap::idx_t tr = l; tr < FUZZ_WINDOW; tr++) {
  81         BitMap::idx_t r = MIN2(BITMAP_SIZE, size_class + tr); // avoid overflow
  82 
  83         map.set_large_range(l, r);
  84         verify_set(map, l, r);
  85         verify_unset(map, 0, l);
  86         verify_unset(map, r, BITMAP_SIZE);
  87 
  88         // Restore set
  89         map.clear_range(l, r);
  90         verify_unset(map, l, r);
  91       }
  92     }
  93   }
  94 }
  95 
  96 TEST(BitMap, par_at_put_large_range) {
  97   CHeapBitMap map(BITMAP_SIZE);
  98 
  99   map.clear();
 100   verify_unset(map, 0, BITMAP_SIZE);
 101 
 102   for (size_t size_class = 0; size_class <= BITMAP_SIZE; size_class = MAX2<size_t>(1, size_class*2)) {
 103     for (BitMap::idx_t l = 0; l < FUZZ_WINDOW; l++) {
 104       for (BitMap::idx_t tr = l; tr < FUZZ_WINDOW; tr++) {
 105         BitMap::idx_t r = MIN2(BITMAP_SIZE, size_class + tr); // avoid overflow
 106 
 107         map.par_at_put_large_range(l, r, true);
 108         verify_set(map, l, r);
 109         verify_unset(map, 0, l);
 110         verify_unset(map, r, BITMAP_SIZE);
 111 
 112         // Restore set
 113         map.clear_range(l, r);
 114         verify_unset(map, l, r);
 115       }
 116     }
 117   }
 118 }