1   /**
2    * Copyright 2011 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import static org.junit.Assert.*;
23  
24  import java.util.List;
25  import java.util.Map;
26  import java.util.Random;
27  import java.util.TreeMap;
28  import java.util.concurrent.atomic.AtomicInteger;
29  
30  import org.apache.hadoop.conf.Configuration;
31  import org.apache.hadoop.hbase.MultithreadedTestUtil;
32  import org.apache.hadoop.hbase.MultithreadedTestUtil.TestThread;
33  import org.apache.hadoop.hbase.regionserver.MemStoreLAB.Allocation;
34  import org.junit.Test;
35  
36  import com.google.common.base.Function;
37  import com.google.common.collect.Iterables;
38  import com.google.common.collect.Lists;
39  import com.google.common.collect.MapMaker;
40  import com.google.common.collect.Maps;
41  import com.google.common.primitives.Ints;
42  import com.google.common.primitives.Longs;
43  
44  public class TestMemStoreLAB {
45  
46    /**
47     * Test a bunch of random allocations
48     */
49    @Test
50    public void testLABRandomAllocation() {
51      Random rand = new Random();
52      MemStoreLAB mslab = new MemStoreLAB();
53      int expectedOff = 0;
54      byte[] lastBuffer = null;
55      // 100K iterations by 0-1K alloc -> 50MB expected
56      // should be reasonable for unit test and also cover wraparound
57      // behavior
58      for (int i = 0; i < 100000; i++) {
59        int size = rand.nextInt(1000);
60        Allocation alloc = mslab.allocateBytes(size);
61        
62        if (alloc.getData() != lastBuffer) {
63          expectedOff = 0;
64          lastBuffer = alloc.getData();
65        }
66        assertEquals(expectedOff, alloc.getOffset());
67        assertTrue("Allocation " + alloc + " overruns buffer",
68            alloc.getOffset() + size <= alloc.getData().length);
69        expectedOff += size;
70      }
71    }
72  
73    @Test
74    public void testLABLargeAllocation() {
75      MemStoreLAB mslab = new MemStoreLAB();
76      Allocation alloc = mslab.allocateBytes(2*1024*1024);
77      assertNull("2MB allocation shouldn't be satisfied by LAB.",
78        alloc);
79    } 
80  
81    /**
82     * Test allocation from lots of threads, making sure the results don't
83     * overlap in any way
84     */
85    @Test
86    public void testLABThreading() throws Exception {
87      Configuration conf = new Configuration();
88      MultithreadedTestUtil.TestContext ctx =
89        new MultithreadedTestUtil.TestContext(conf);
90      
91      final AtomicInteger totalAllocated = new AtomicInteger();
92      
93      final MemStoreLAB mslab = new MemStoreLAB();
94      List<List<AllocRecord>> allocations = Lists.newArrayList();
95      
96      for (int i = 0; i < 10; i++) {
97        final List<AllocRecord> allocsByThisThread = Lists.newLinkedList();
98        allocations.add(allocsByThisThread);
99        
100       TestThread t = new MultithreadedTestUtil.RepeatingTestThread(ctx) {
101         private Random r = new Random();
102         @Override
103         public void doAnAction() throws Exception {
104           int size = r.nextInt(1000);
105           Allocation alloc = mslab.allocateBytes(size);
106           totalAllocated.addAndGet(size);
107           allocsByThisThread.add(new AllocRecord(alloc, size));
108         }
109       };
110       ctx.addThread(t);
111     }
112     
113     ctx.startThreads();
114     while (totalAllocated.get() < 50*1024*1024 && ctx.shouldRun()) {
115       Thread.sleep(10);
116     }
117     ctx.stop();
118     
119     // Partition the allocations by the actual byte[] they point into,
120     // make sure offsets are unique for each chunk
121     Map<byte[], Map<Integer, AllocRecord>> mapsByChunk =
122       Maps.newHashMap();
123     
124     int sizeCounted = 0;
125     for (AllocRecord rec : Iterables.concat(allocations)) {
126       sizeCounted += rec.size;
127       if (rec.size == 0) continue;
128       
129       Map<Integer, AllocRecord> mapForThisByteArray =
130         mapsByChunk.get(rec.alloc.getData());
131       if (mapForThisByteArray == null) {
132         mapForThisByteArray = Maps.newTreeMap();
133         mapsByChunk.put(rec.alloc.getData(), mapForThisByteArray);
134       }
135       AllocRecord oldVal = mapForThisByteArray.put(rec.alloc.getOffset(), rec);
136       assertNull("Already had an entry " + oldVal + " for allocation " + rec,
137           oldVal);
138     }
139     assertEquals("Sanity check test", sizeCounted, totalAllocated.get());
140     
141     // Now check each byte array to make sure allocations don't overlap
142     for (Map<Integer, AllocRecord> allocsInChunk : mapsByChunk.values()) {
143       int expectedOff = 0;
144       for (AllocRecord alloc : allocsInChunk.values()) {
145         assertEquals(expectedOff, alloc.alloc.getOffset());
146         assertTrue("Allocation " + alloc + " overruns buffer",
147             alloc.alloc.getOffset() + alloc.size <= alloc.alloc.getData().length);
148         expectedOff += alloc.size;
149       }
150     }
151 
152   }
153   
154   private static class AllocRecord implements Comparable<AllocRecord>{
155     private final Allocation alloc;
156     private final int size;
157     public AllocRecord(Allocation alloc, int size) {
158       super();
159       this.alloc = alloc;
160       this.size = size;
161     }
162 
163     @Override
164     public int compareTo(AllocRecord e) {
165       if (alloc.getData() != e.alloc.getData()) {
166         throw new RuntimeException("Can only compare within a particular array");
167       }
168       return Ints.compare(alloc.getOffset(), e.alloc.getOffset());
169     }
170     
171     @Override
172     public String toString() {
173       return "AllocRecord(alloc=" + alloc + ", size=" + size + ")";
174     }
175     
176   }
177 }