/** * Test a bunch of random allocations */ @Test public void testLABRandomAllocation() { Random rand = new Random(); MemStoreLAB mslab = new HeapMemStoreLAB(); int expectedOff = 0; byte[] lastBuffer = null; // 100K iterations by 0-1K alloc -> 50MB expected // should be reasonable for unit test and also cover wraparound // behavior for (int i = 0; i < 100000; i++) { int size = rand.nextInt(1000); ByteRange alloc = mslab.allocateBytes(size); if (alloc.getBytes() != lastBuffer) { expectedOff = 0; lastBuffer = alloc.getBytes(); } assertEquals(expectedOff, alloc.getOffset()); assertTrue("Allocation overruns buffer", alloc.getOffset() + size <= alloc.getBytes().length); expectedOff += size; } }
/** * Called when we need to convert a leaf node into a branch with 2 leaves. Comments inside the * method assume we have token BAA starting at tokenStartOffset=0 and are adding BOO. The output * will be 3 nodes:<br> * <ul> * <li>1: B <- branch * <li>2: AA <- leaf * <li>3: OO <- leaf * </ul> * * @param numTokenBytesToRetain => 1 (the B) * @param bytes => BOO */ protected void split(int numTokenBytesToRetain, final ByteRange bytes) { int childNodeDepth = nodeDepth; int childTokenStartOffset = tokenStartOffset + numTokenBytesToRetain; //create leaf AA TokenizerNode firstChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, token, numTokenBytesToRetain); firstChild.setNumOccurrences(numOccurrences);// do before clearing this node's numOccurrences token.setLength(numTokenBytesToRetain);//shorten current token from BAA to B numOccurrences = 0;//current node is now a branch moveChildrenToDifferentParent(firstChild);//point the new leaf (AA) to the new branch (B) addChild(firstChild);//add the new leaf (AA) to the branch's (B's) children //create leaf OO TokenizerNode secondChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tokenStartOffset + numTokenBytesToRetain); addChild(secondChild);//add the new leaf (00) to the branch's (B's) children // we inserted branch node B as a new level above/before the two children, so increment the // depths of the children below firstChild.incrementNodeDepthRecursively(); secondChild.incrementNodeDepthRecursively(); }
protected TokenizerNode addNode(TokenizerNode parent, int nodeDepth, int tokenStartOffset, final ByteRange token, int inputTokenOffset) { int inputTokenLength = token.getLength() - inputTokenOffset; int tokenOffset = appendTokenAndRepointByteRange(token, inputTokenOffset); TokenizerNode node = null; if (nodes.size() <= numNodes) { node = new TokenizerNode(this, parent, nodeDepth, tokenStartOffset, tokenOffset, inputTokenLength); nodes.add(node); } else { node = nodes.get(numNodes); node.reset(); node.reconstruct(this, parent, nodeDepth, tokenStartOffset, tokenOffset, inputTokenLength); } ++numNodes; return node; }
protected int store(ByteRange bytes) { int indexOfNewElement = numUniqueRanges; if (uniqueRanges.size() <= numUniqueRanges) { uniqueRanges.add(new SimpleMutableByteRange()); } ByteRange storedRange = uniqueRanges.get(numUniqueRanges); int neededBytes = numBytes + bytes.getLength(); byteAppender = ArrayUtils.growIfNecessary(byteAppender, neededBytes, 2 * neededBytes); bytes.deepCopyTo(byteAppender, numBytes); storedRange.set(byteAppender, numBytes, bytes.getLength());// this isn't valid yet numBytes += bytes.getLength(); uniqueIndexByUniqueRange.put(storedRange, indexOfNewElement); int newestUniqueIndex = numUniqueRanges; ++numUniqueRanges; return newestUniqueIndex; }
/***************** standard methods ************************/ @Override public String toString() { StringBuilder sb = new StringBuilder(); int i = 0; for (ByteRange r : sortedRanges) { if (i > 0) { sb.append("\n"); } sb.append(i + " " + Bytes.toStringBinary(r.deepCopyToNewArray())); ++i; } sb.append("\ntotalSize:" + numBytes); sb.append("\navgSize:" + getAvgSize()); return sb.toString(); }
/** * Called when we need to convert a leaf node into a branch with 2 leaves. Comments inside the * method assume we have token BAA starting at tokenStartOffset=0 and are adding BOO. The output * will be 3 nodes:<br/> * <li>1: B <- branch * <li>2: AA <- leaf * <li>3: OO <- leaf * * @param numTokenBytesToRetain => 1 (the B) * @param bytes => BOO */ protected void split(int numTokenBytesToRetain, final ByteRange bytes) { int childNodeDepth = nodeDepth; int childTokenStartOffset = tokenStartOffset + numTokenBytesToRetain; //create leaf AA TokenizerNode firstChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, token, numTokenBytesToRetain); firstChild.setNumOccurrences(numOccurrences);// do before clearing this node's numOccurrences token.setLength(numTokenBytesToRetain);//shorten current token from BAA to B numOccurrences = 0;//current node is now a branch moveChildrenToDifferentParent(firstChild);//point the new leaf (AA) to the new branch (B) addChild(firstChild);//add the new leaf (AA) to the branch's (B's) children //create leaf OO TokenizerNode secondChild = builder.addNode(this, childNodeDepth, childTokenStartOffset, bytes, tokenStartOffset + numTokenBytesToRetain); addChild(secondChild);//add the new leaf (00) to the branch's (B's) children // we inserted branch node B as a new level above/before the two children, so increment the // depths of the children below firstChild.incrementNodeDepthRecursively(); secondChild.incrementNodeDepthRecursively(); }
protected int store(ByteRange bytes) { int indexOfNewElement = numUniqueRanges; if (uniqueRanges.size() <= numUniqueRanges) { uniqueRanges.add(new SimpleByteRange()); } ByteRange storedRange = uniqueRanges.get(numUniqueRanges); int neededBytes = numBytes + bytes.getLength(); byteAppender = ArrayUtils.growIfNecessary(byteAppender, neededBytes, 2 * neededBytes); bytes.deepCopyTo(byteAppender, numBytes); storedRange.set(byteAppender, numBytes, bytes.getLength());// this isn't valid yet numBytes += bytes.getLength(); uniqueIndexByUniqueRange.put(storedRange, indexOfNewElement); int newestUniqueIndex = numUniqueRanges; ++numUniqueRanges; return newestUniqueIndex; }
public VisibilityLabelFilter(VisibilityExpEvaluator expEvaluator, Map<ByteRange, Integer> cfVsMaxVersions) { this.expEvaluator = expEvaluator; this.cfVsMaxVersions = cfVsMaxVersions; this.curFamily = new SimpleMutableByteRange(); this.curQualifier = new SimpleMutableByteRange(); }
public static Filter createVisibilityLabelFilter(Region region, Authorizations authorizations) throws IOException { Map<ByteRange, Integer> cfVsMaxVersions = new HashMap<ByteRange, Integer>(); for (HColumnDescriptor hcd : region.getTableDesc().getFamilies()) { cfVsMaxVersions.put(new SimpleMutableByteRange(hcd.getName()), hcd.getMaxVersions()); } VisibilityLabelService vls = VisibilityLabelServiceManager.getInstance() .getVisibilityLabelService(); Filter visibilityLabelFilter = new VisibilityLabelFilter( vls.getVisibilityExpEvaluator(authorizations), cfVsMaxVersions); return visibilityLabelFilter; }
AccessControlFilter(TableAuthManager mgr, User ugi, TableName tableName, Strategy strategy, Map<ByteRange, Integer> cfVsMaxVersions) { authManager = mgr; table = tableName; user = ugi; isSystemTable = tableName.isSystemTable(); this.strategy = strategy; this.cfVsMaxVersions = cfVsMaxVersions; this.prevFam = new SimpleMutableByteRange(); this.prevQual = new SimpleMutableByteRange(); }
/** * Allocate a slice of the given length. * * If the size is larger than the maximum size specified for this * allocator, returns null. */ @Override public ByteRange allocateBytes(int size) { Preconditions.checkArgument(size >= 0, "negative size"); // Callers should satisfy large allocations directly from JVM since they // don't cause fragmentation as badly. if (size > maxAlloc) { return null; } while (true) { Chunk c = getOrMakeChunk(); // Try to allocate from this chunk int allocOffset = c.alloc(size); if (allocOffset != -1) { // We succeeded - this is the common case - small alloc // from a big buffer return new SimpleMutableByteRange(c.data, allocOffset, size); } // not enough space! // try to retire this chunk tryRetireChunk(c); } }
@Test public void testLABLargeAllocation() { MemStoreLAB mslab = new HeapMemStoreLAB(); ByteRange alloc = mslab.allocateBytes(2*1024*1024); assertNull("2MB allocation shouldn't be satisfied by LAB.", alloc); }
@Test public void testReusingChunks() { Random rand = new Random(); MemStoreLAB mslab = new HeapMemStoreLAB(conf); int expectedOff = 0; byte[] lastBuffer = null; // Randomly allocate some bytes for (int i = 0; i < 100; i++) { int size = rand.nextInt(1000); ByteRange alloc = mslab.allocateBytes(size); if (alloc.getBytes() != lastBuffer) { expectedOff = 0; lastBuffer = alloc.getBytes(); } assertEquals(expectedOff, alloc.getOffset()); assertTrue("Allocation overruns buffer", alloc.getOffset() + size <= alloc.getBytes().length); expectedOff += size; } // chunks will be put back to pool after close mslab.close(); int chunkCount = chunkPool.getPoolSize(); assertTrue(chunkCount > 0); // reconstruct mslab mslab = new HeapMemStoreLAB(conf); // chunk should be got from the pool, so we can reuse it. mslab.allocateBytes(1000); assertEquals(chunkCount - 1, chunkPool.getPoolSize()); }
/***************** building *************************/ public void addAll(ArrayList<ByteRange> sortedByteRanges) { for (int i = 0; i < sortedByteRanges.size(); ++i) { ByteRange byteRange = sortedByteRanges.get(i); addSorted(byteRange); } }
public void addSorted(final ByteRange bytes) { ++numArraysAdded; if (bytes.getLength() > maxElementLength) { maxElementLength = bytes.getLength(); } if (root == null) { // nodeDepth of firstNode (non-root) is 1 root = addNode(null, 1, 0, bytes, 0); } else { root.addSorted(bytes); } }
protected int appendTokenAndRepointByteRange(final ByteRange token, int inputTokenOffset) { int newOffset = tokensLength; int inputTokenLength = token.getLength() - inputTokenOffset; int newMinimum = tokensLength + inputTokenLength; tokens = ArrayUtils.growIfNecessary(tokens, newMinimum, 2 * newMinimum); token.deepCopySubRangeTo(inputTokenOffset, inputTokenLength, tokens, tokensLength); tokensLength += inputTokenLength; return newOffset; }
/** * Check if the incoming byte range exists. If not, add it to the backing byteAppender[] and * insert it into the tracking Map uniqueIndexByUniqueRange. */ public void add(ByteRange bytes) { Integer index = uniqueIndexByUniqueRange.get(bytes); if (index == null) { index = store(bytes); } int minLength = numInputs + 1; uniqueRangeIndexByInsertionId = ArrayUtils.growIfNecessary(uniqueRangeIndexByInsertionId, minLength, 2 * minLength); uniqueRangeIndexByInsertionId[numInputs] = index; ++numInputs; }
@Override public List<ByteRange> getInputs() { List<String> d = Lists.newArrayList(); d.add("abc"); d.add("abcde"); d.add("abc"); d.add("bbc"); d.add("abc"); return ByteRangeUtils.fromArrays(Bytes.getUtf8ByteArrays(d)); }
@Override public List<ByteRange> getOutputs() { List<String> d = Lists.newArrayList(); d.add("abc"); d.add("abcde"); d.add("bbc"); return ByteRangeUtils.fromArrays(Bytes.getUtf8ByteArrays(d)); }
/*************** construct ****************************/ public TestColumnBuilder(TestColumnData columns) { this.columns = columns; List<ByteRange> inputs = columns.getInputs(); this.columnSorter = new ByteRangeTreeSet(inputs); this.sortedUniqueColumns = columnSorter.compile().getSortedRanges(); List<byte[]> copies = ByteRangeUtils.copyToNewArrays(sortedUniqueColumns); Assert.assertTrue(Bytes.isSorted(copies)); this.blockMeta = new PrefixTreeBlockMeta(); this.blockMeta.setNumMetaBytes(0); this.blockMeta.setNumRowBytes(0); this.builder = new Tokenizer(); }
public static Filter createVisibilityLabelFilter(HRegion region, Authorizations authorizations) throws IOException { Map<ByteRange, Integer> cfVsMaxVersions = new HashMap<ByteRange, Integer>(); for (HColumnDescriptor hcd : region.getTableDesc().getFamilies()) { cfVsMaxVersions.put(new SimpleMutableByteRange(hcd.getName()), hcd.getMaxVersions()); } VisibilityLabelService vls = VisibilityLabelServiceManager.getInstance() .getVisibilityLabelService(); Filter visibilityLabelFilter = new VisibilityLabelFilter( vls.getVisibilityExpEvaluator(authorizations), cfVsMaxVersions); return visibilityLabelFilter; }
