mirror of https://github.com/OpenIdentityPlatform/OpenDJ.git
opendj-server-legacy/src/main/java/org/opends/server/api/CompressedSchema.java
@@ -21,6 +21,8 @@ import static org.opends.server.util.StaticUtils.bytesToHexNoSpace; import java.util.AbstractMap.SimpleImmutableEntry; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Iterator; @@ -45,6 +47,7 @@ import org.forgerock.opendj.ldap.schema.AttributeType; import org.forgerock.opendj.ldap.schema.ObjectClass; import org.forgerock.opendj.ldap.schema.Schema; import org.forgerock.util.annotations.VisibleForTesting; import org.opends.server.core.DirectoryServer; import org.opends.server.core.ServerContext; import org.opends.server.types.Attribute; @@ -94,6 +97,29 @@ /** The most bytes {@link #encodeId(int)} ever writes a schema element ID in. */ private static final int MAX_ID_BYTES = 4; /** * The highest ID a definition may be loaded under. * <p> * The decode maps are indexed by the ID, so an ID read out of a storage is also the size the map * has to be padded to, and the padding runs under {@link #exclusiveLock} while a backend opens. * Nothing in a token says whether the ID it folds to is one this server allocated or one a * corrupt record composed, so the ceiling is what keeps the second from costing the memory of the * first: four bytes address two billion slots, and {@link #encodeId(int)} writes four of them for * every ID past 16777214, so a truncated or partially written record is enough to name one. * <p> * An ID is allocated per distinct attribute description - the type together with its options - * and per distinct object class set, once and for the life of the storage. A deployment encodes * those in the hundreds, and a large one in the thousands, so this leaves a hundredfold headroom * over what a compressed schema is asked to hold. Above it a definition is skipped and reported: * a definition wrongly skipped is one the decode path reports as an unknown token, which is loud, * whereas an ID taken at face value is an open that does not finish. * <p> * The same ceiling bounds what {@link #allocatable(int)} hands out, and it has to: a token this * schema writes but would not take back leaves an entry that cannot be decoded after a restart. */ @VisibleForTesting static final int MAX_LOAD_ID = 1 << 20; private final ServerContext serverContext; /** Lock serializing all mutations (id registration and schema reload). */ private final ReentrantLock exclusiveLock = new ReentrantLock(); @@ -143,8 +169,8 @@ // build new maps from one stable snapshot of the existing ones final Mappings oldMappings = mappings; Mappings newMappings = new Mappings(oldMappings.adEncodeMap.size(), oldMappings.ocEncodeMap.size()); reloadAttributeTypeMaps(oldMappings, newMappings); reloadObjectClassesMap(oldMappings, newMappings); reloadAttributeTypeMaps(oldMappings, newMappings, currentSchema); reloadObjectClassesMap(oldMappings, newMappings, currentSchema); mappings = newMappings; schema = currentSchema; @@ -161,44 +187,68 @@ * Reload the attribute types maps. This should be called when schema has changed, because some * types may be out dated. */ private void reloadAttributeTypeMaps(Mappings mappings, Mappings newMappings) private void reloadAttributeTypeMaps(Mappings mappings, Mappings newMappings, Schema newSchema) { for(int id=0;id<mappings.adDecodeMap.size();id++){ // Built whole and handed to the decode map in one go: it is a CopyOnWriteArrayList, so // appending the elements one at a time copies the whole backing array per element, and this // walks every id the compressed schema holds while readers of every backend wait on the lock. final int size = mappings.adDecodeMap.size(); final List<AttributeDescription> reloaded = new ArrayList<>(size); for (int id = 0; id < size; id++) { final AttributeDescription ad = mappings.adDecodeMap.get(id); if (ad != null) { loadAttributeToMaps(id, ad.getAttributeType().getNameOrOID(), ad.getOptions(), newMappings); } else if (ad == null) { // A decode map can carry a gap: it is padded with null for the ids missing from the // compressed schema it was loaded from. Carry the gap over rather than dereferencing it, // and carry it over as a gap - dropping it would shift the ids of the elements after it, // and would let the next registration hand out an id an already written entry carries. // The ids are walked in order from zero, so the new map holds exactly id elements here. newMappings.adDecodeMap.add(null); // compressed schema it was loaded from, and for the ids of the definitions it skipped. // Carried over rather than dereferenced, and carried over as a gap - dropping it would // shift the ids of the elements after it, and would let the next registration hand out an // id an already written entry carries. reloaded.add(null); continue; } final AttributeDescription reloadedAd = AttributeDescription.create( newSchema.getAttributeType(ad.getAttributeType().getNameOrOID()), getOptions(ad.getOptions())); newMappings.adEncodeMap.put(reloadedAd, id); reloaded.add(reloadedAd); } newMappings.adDecodeMap.addAll(reloaded); } /** * Reload the object classes maps. This should be called when schema has changed, because some * classes may be out dated. */ private void reloadObjectClassesMap(Mappings mappings, Mappings newMappings) private void reloadObjectClassesMap(Mappings mappings, Mappings newMappings, Schema newSchema) { for(int id=0;id<mappings.ocDecodeMap.size();id++){ // Built whole and handed over in one go, and the gaps are carried, as in // reloadAttributeTypeMaps(). final int size = mappings.ocDecodeMap.size(); final List<Map<ObjectClass, String>> reloaded = new ArrayList<>(size); for (int id = 0; id < size; id++) { final Map<ObjectClass, String> ocMap = mappings.ocDecodeMap.get(id); if (ocMap != null) if (ocMap == null) { loadObjectClassesToMaps(id, ocMap.values(), newMappings, false); reloaded.add(null); continue; } else { // A gap, as in reloadAttributeTypeMaps(). newMappings.ocDecodeMap.add(null); } final Map<ObjectClass, String> reloadedOcMap = objectClassMap(newSchema, ocMap.values()); newMappings.ocEncodeMap.put(reloadedOcMap, id); reloaded.add(reloadedOcMap); } newMappings.ocDecodeMap.addAll(reloaded); } /** The object class set a compressed schema holds for the provided names, resolved against a schema. */ private static Map<ObjectClass, String> objectClassMap(final Schema schema, final Collection<String> names) { final LinkedHashMap<ObjectClass, String> ocMap = new LinkedHashMap<>(names.size()); for (final String name : names) { ocMap.put(schema.getObjectClass(name), name); } return ocMap; } /** @@ -394,7 +444,7 @@ */ private int registerAttribute(final Mappings mappings, final AttributeDescription ad) throws DirectoryException { final int id = mappings.adDecodeMap.size(); final int id = allocatable(mappings.adDecodeMap.size()); // Appended to the decode map first: storeAttribute() is free to persist the whole content of // this compressed schema rather than the single element it is handed - DefaultCompressedSchema // rewrites its file from getAllAttributes() - so the element being registered has to be part @@ -530,7 +580,7 @@ private int registerObjectClasses(final Mappings mappings, final Map<ObjectClass, String> objectClasses) throws DirectoryException { final int id = mappings.ocDecodeMap.size(); final int id = allocatable(mappings.ocDecodeMap.size()); mappings.ocDecodeMap.add(objectClasses); boolean registered = false; try @@ -693,17 +743,115 @@ * The user provided attribute type name. * @param attributeOptions * The non-null but possibly empty set of attribute options. * @return The attribute type description. * @return The attribute type description, or {@code null} if the definition was skipped because * the key it is stored under is not one a compressed schema hands out. */ protected final AttributeDescription loadAttribute( final byte[] encodedAttribute, final String attributeName, final Collection<String> attributeOptions) { final int id = decodeId(encodedAttribute); if (!isLoadable(encodedAttribute, id)) { logger.error(ERR_COMPRESSEDSCHEMA_UNUSABLE_AD_TOKEN, attributeName, tokenInMessage(encodedAttribute, id)); reserve(getMappings().adDecodeMap, id); return null; } return loadAttributeToMaps(id, attributeName, attributeOptions, getMappings()); } /** * Tells whether a definition may be loaded under the key a storage holds it under, which is the * one thing the load path knows about that key: {@link #decodeId(byte[])} folds whatever it is * handed, so every key reads as an ID and nothing after this can tell one a compressed schema * wrote from one a corrupt or truncated record composed. A record failing this is skipped rather * than loaded - the ID it names is left with no definition, which the decode path already * reports - because the alternative is an open that fails or never finishes for one bad record. * <p> * The key has to be the one {@link #encodeId(int)} writes for the ID it folds to. A key padded * with leading zeros, or longer than the four bytes an ID is ever written in, folds to the ID its * canonical key addresses, and loading it would displace the definition that ID belongs to: the * decode map is only overwritten there, so entries carrying that token would go on decoding, as * another attribute description. The sign is checked on its own because the canonical key of the * ID -1 is the all-zero key that folds to it, and an ID is checked against * {@link #MAX_LOAD_ID} because the decode map is padded up to it. * * @param idBytes * The key the definition is stored under. * @param id * The ID that key folds to. * @return {@code true} if the definition may be loaded under that key. */ private boolean isLoadable(final byte[] idBytes, final int id) { return id >= 0 && id <= MAX_LOAD_ID && Arrays.equals(idBytes, encodeId(id)); } /** * Returns the ID a registration is about to allocate, having checked that a load would take it * back. An ID past {@link #MAX_LOAD_ID} is refused rather than handed out: an entry written under * a token the next open skips cannot be decoded once the server is restarted, which is the same * reason a registration whose store failed is withdrawn rather than published. * <p> * Only reachable where a stored definition named an ID near the ceiling - no registration walks * there on its own, since every ID it hands out is the size of a map it grows one element at a * time - so this reports a storage to be exported and imported again rather than a limit a * running server is expected to meet. * * @param id * The ID the registration would allocate. * @return That ID. * @throws DirectoryException * If no load would take a definition back under it. */ private static int allocatable(final int id) throws DirectoryException { if (id > MAX_LOAD_ID) { throw new DirectoryException(DirectoryServer.getCoreConfigManager().getServerErrorResultCode(), ERR_COMPRESSEDSCHEMA_NO_TOKEN_LEFT.get(id, MAX_LOAD_ID)); } return id; } /** * Holds the ID of a definition that was skipped, so that no registration hands it out again. * <p> * A key mangled from the one it was written under folds to the ID that key addressed, and the * entries carrying that ID are still in the backend. Were the ID left out of the decode map, the * next registration would take it - a registration takes the size of the map - and those entries * would decode as whatever it stored, silently. Held as the gap it is, they are reported as the * unknown token they now carry instead, which is what the decode path does with a gap. * <p> * An ID that no registration can reach is not held: a negative one is no index at all, and one * past {@link #MAX_LOAD_ID} is one {@link #registerAttribute} refuses to allocate, so neither can * be handed out to begin with and padding a map up to either is the cost this ceiling exists to * refuse. * * @param decodeMap * The decode map the skipped definition would have gone into. * @param id * The ID its key folds to. */ private <T> void reserve(final List<T> decodeMap, final int id) { if (id < 0 || id > MAX_LOAD_ID) { return; } exclusiveLock.lock(); try { padTo(decodeMap, id + 1); } finally { exclusiveLock.unlock(); } } /** * Loads an attribute into provided encode and decode maps, given its id, name, and options. * * @param id @@ -719,8 +867,7 @@ private AttributeDescription loadAttributeToMaps(final int id, final String attributeName, final Iterable<String> attributeOptions, final Mappings mappings) { Schema schema2 = DirectoryServer.getInstance().getServerContext().getSchema(); final AttributeType type = schema2.getAttributeType(attributeName); final AttributeType type = serverContext.getSchema().getAttributeType(attributeName); final Set<String> options = getOptions(attributeOptions); final AttributeDescription ad = AttributeDescription.create(type, options); exclusiveLock.lock(); @@ -733,11 +880,8 @@ } else { // Grow the decode array. while (id > mappings.adDecodeMap.size()) { mappings.adDecodeMap.add(null); } // Grow the decode array, in one pass rather than a slot at a time. padTo(mappings.adDecodeMap, id); mappings.adDecodeMap.add(ad); } return ad; @@ -778,14 +922,22 @@ * The encoded object classes. * @param objectClassNames * The user provided set of object class names. * @return The object class set. * @return The object class set, or {@code null} if the definition was skipped because the key it * is stored under is not one a compressed schema hands out. */ protected final Map<ObjectClass, String> loadObjectClasses( final byte[] encodedObjectClasses, final Collection<String> objectClassNames) { final int id = decodeId(encodedObjectClasses); return loadObjectClassesToMaps(id, objectClassNames, mappings, true); if (!isLoadable(encodedObjectClasses, id)) { logger.error(ERR_COMPRESSEDSCHEMA_UNUSABLE_OC_TOKEN, objectClassNames, tokenInMessage(encodedObjectClasses, id)); reserve(getMappings().ocDecodeMap, id); return null; } return loadObjectClassesToMaps(id, objectClassNames, mappings); } /** @@ -804,34 +956,23 @@ * indicates if update of maps should be synchronized * @return The object class set. */ private final Map<ObjectClass, String> loadObjectClassesToMaps(int id, final Collection<String> objectClassNames, Mappings mappings, boolean sync) private Map<ObjectClass, String> loadObjectClassesToMaps(int id, final Collection<String> objectClassNames, Mappings mappings) { final LinkedHashMap<ObjectClass, String> ocMap = new LinkedHashMap<>(objectClassNames.size()); for (final String name : objectClassNames) { ocMap.put(DirectoryServer.getInstance().getServerContext().getSchema().getObjectClass(name), name); } if (sync) { exclusiveLock.lock(); try { updateObjectClassesMaps(id, mappings, ocMap); } finally { exclusiveLock.unlock(); } } else final Map<ObjectClass, String> ocMap = objectClassMap(serverContext.getSchema(), objectClassNames); exclusiveLock.lock(); try { updateObjectClassesMaps(id, mappings, ocMap); } finally { exclusiveLock.unlock(); } return ocMap; } private void updateObjectClassesMaps(int id, Mappings mappings, LinkedHashMap<ObjectClass, String> ocMap) private void updateObjectClassesMaps(int id, Mappings mappings, Map<ObjectClass, String> ocMap) { mappings.ocEncodeMap.put(ocMap, id); if (id < mappings.ocDecodeMap.size()) @@ -840,16 +981,37 @@ } else { // Grow the decode array. while (id > mappings.ocDecodeMap.size()) { mappings.ocDecodeMap.add(null); } // Grow the decode array, in one pass rather than a slot at a time. padTo(mappings.ocDecodeMap, id); mappings.ocDecodeMap.add(ocMap); } } /** * Pads a decode map with the slots of the IDs it holds no definition for, up to the provided * size, and leaves a map already that long alone. * <p> * In one pass, because a decode map is a {@link CopyOnWriteArrayList}: appending the slots one at * a time copies the whole backing array per slot, so padding a map to an ID costs the square of * it. That is paid under {@link #exclusiveLock}, and for the pluggable backends inside the write * transaction the root container opens in, where nothing says what the open is waiting for - and * the IDs are read out of a storage, so how far a map is padded is not this server's to choose. * * @param decodeMap * The decode map to pad. * @param size * The size to pad it to. */ private static <T> void padTo(final List<T> decodeMap, final int size) { final int missing = size - decodeMap.size(); if (missing > 0) { decodeMap.addAll(Collections.<T> nCopies(missing, null)); } } /** * Persists the provided encoded attribute. The default implementation is to * do nothing. Calls to this method are synchronized, so implementations can * assume that this method is not being called by other threads. Note that @@ -1018,13 +1180,15 @@ } /** * Encodes the provided schema element ID. * Encodes the provided schema element ID, in as few bytes as it fits in - which is what * {@link #isLoadable(byte[], int)} holds a stored key to, so nothing else may encode one. * * @param id * The schema element ID. * @return The encoded schema element ID. */ private byte[] encodeId(final int id) @VisibleForTesting static byte[] encodeId(final int id) { final int value = id + 1; // Add 1 to compensate for old behavior. final byte[] idBytes; opendj-server-legacy/src/messages/org/opends/messages/core.properties
@@ -1086,6 +1086,22 @@ ERR_COMPRESSEDSCHEMA_UNREADABLE_OC_TOKEN_758=Unable to decode the \ provided object class set because its token could not be read from the \ record: %s ERR_COMPRESSEDSCHEMA_UNUSABLE_AD_TOKEN_760=The stored compressed schema \ definition of the attribute type '%s' has been skipped because the token %s \ it is stored under is not one a compressed schema hands out. Entries \ carrying that token will be reported as using an undefined attribute \ description token ERR_COMPRESSEDSCHEMA_NO_TOKEN_LEFT_762=The compressed schema cannot allocate \ a token for a new definition: the next one would be the id %s, and a \ definition is only ever loaded back under an id of at most %s. A token this \ high is only ever reached where a stored definition named an id no \ compressed schema hands out, so the storage holding it should be exported \ and imported again ERR_COMPRESSEDSCHEMA_UNUSABLE_OC_TOKEN_761=The stored compressed schema \ definition of the object classes %s has been skipped because the token %s \ it is stored under is not one a compressed schema hands out. Entries \ carrying that token will be reported as using an undefined object class \ token ERR_ENTRYENCODECFG_INVALID_LENGTH_623=Unable to decode the provided \ entry encode configuration element because it has an invalid length INFO_RESULT_NO_OPERATION_624=No Operation opendj-server-legacy/src/test/java/org/opends/server/api/CompressedSchemaTestCase.java
@@ -16,6 +16,8 @@ package org.opends.server.api; import static org.opends.messages.CoreMessages.*; import static org.opends.server.api.CompressedSchema.MAX_LOAD_ID; import static org.opends.server.util.StaticUtils.bytesToHexNoSpace; import static org.testng.Assert.*; import java.util.ArrayList; @@ -35,6 +37,7 @@ import java.util.concurrent.atomic.AtomicReference; import org.forgerock.i18n.LocalizableMessage; import org.forgerock.opendj.ldap.AttributeDescription; import org.forgerock.opendj.ldap.ByteString; import org.forgerock.opendj.ldap.ByteStringBuilder; import org.forgerock.opendj.ldap.ByteSequenceReader; @@ -134,6 +137,21 @@ loadObjectClasses(encodedToken(id), objectClassNames); } /** * Loads a definition under the provided key, as an implementation does at startup for every * record it read - the key being whatever the storage holds rather than one this test composed. */ private AttributeDescription loadAttributeUnder(final byte[] token, final String attributeName) { return loadAttribute(token, attributeName, Collections.<String> emptySet()); } private Map<ObjectClass, String> loadObjectClassesUnder(final byte[] token, final Collection<String> objectClassNames) { return loadObjectClasses(token, objectClassNames); } /** The tokens the whole content would be saved under, as DefaultCompressedSchema saves it. */ private List<Integer> savedAttributeTokens() { @@ -594,6 +612,270 @@ } } /** * A definition stored under a key no compressed schema hands out is skipped rather than loaded. * The load path folds whatever key the storage holds into an id and hands it straight to the * decode map, so a corrupt or truncated key reached that map as a negative index, or - where it * folds to an id that is live - as an overwrite of the definition that id belongs to. One * unreadable record must cost the definition it carries and nothing else: the open goes on, and * the token it was stored under is left with no definition, which the decode path reports. */ @Test public void aTokenNoCompressedSchemaHandsOutIsSkippedWhenLoaded() throws Exception { for (final byte[] unusable : unusableTokens()) { final String token = "0x" + bytesToHexNoSpace(unusable); final TestCompressedSchema compressedSchema = new TestCompressedSchema(); compressedSchema.loadAttributeAt(0, "description"); compressedSchema.loadObjectClassesAt(0, Arrays.asList("top", "person")); assertNull(compressedSchema.loadAttributeUnder(unusable, "cn"), "the attribute description stored under " + token + " should have been skipped"); assertNull(compressedSchema.loadObjectClassesUnder(unusable, Arrays.asList("top", "organizationalUnit")), "the object classes stored under " + token + " should have been skipped"); assertEquals(compressedSchema.savedAttributeTokens(), Collections.singletonList(0), "the definition stored under " + token + " reached the attribute description maps"); assertEquals(compressedSchema.savedObjectClassTokens(), Collections.singletonList(0), "the definition stored under " + token + " reached the object class maps"); assertEquals(attributeNameAt(compressedSchema, 0), "description", "the definition stored under " + token + " displaced the one the id 0 belongs to"); assertEquals(objectClassesAt(compressedSchema, 0), objectClasses("top", "person"), "the definition stored under " + token + " displaced the one the id 0 belongs to"); } } /** * A key folding to an id past the highest one a definition may be loaded under is skipped. The * decode map is indexed by the id, so loading one under an id of that size pads the map up to it, * and it happens under the exclusive lock - inside the write transaction a pluggable backend * opens in, where nothing reports what the open is waiting for. */ @Test public void aTokenBeyondTheHighestLoadableIdIsSkipped() throws Exception { final List<byte[]> beyond = Arrays.asList( encodedToken(MAX_LOAD_ID + 1), // The largest id a four byte key folds to, which is what the issue this guards was raised // for: two billion slots, appended one at a time. new byte[] { (byte) 0x7F, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF }); for (final byte[] unusable : beyond) { final String token = "0x" + bytesToHexNoSpace(unusable); final TestCompressedSchema compressedSchema = new TestCompressedSchema(); assertNull(compressedSchema.loadAttributeUnder(unusable, "description"), "the attribute description stored under " + token + " should have been skipped"); assertNull(compressedSchema.loadObjectClassesUnder(unusable, Arrays.asList("top", "person")), "the object classes stored under " + token + " should have been skipped"); assertEquals(compressedSchema.savedAttributeTokens(), Collections.<Integer> emptyList(), "the definition stored under " + token + " reached the attribute description maps"); assertEquals(compressedSchema.savedObjectClassTokens(), Collections.<Integer> emptyList(), "the definition stored under " + token + " reached the object class maps"); } } /** * The decode map is padded to the id of a definition in one pass, and rebuilt in one pass when * the schema changes. It is a {@link java.util.concurrent.CopyOnWriteArrayList}, so appending the * slots of the ids with no definition one at a time copies the whole backing array per slot: the * highest id a definition may be loaded under is what a corrupt key can still cost an open, and * a quadratic cost there is one an open never finishes paying. */ @Test public void theDecodeMapIsPaddedToALoadedAttributeIdInOnePass() throws Exception { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); final long loadStart = System.nanoTime(); assertNotNull(compressedSchema.loadAttributeUnder(encodedToken(MAX_LOAD_ID), "description"), "the highest loadable id is one an encode hands out and its definition was skipped"); final long loadMs = millisSince(loadStart); // The first decode rebuilds the maps for the current schema, walking the whole decode map. final long decodeStart = System.nanoTime(); final Attribute decoded = compressedSchema.decodeAttribute(recordWithToken(encodedToken(MAX_LOAD_ID), true).asReader()); final long decodeMs = millisSince(decodeStart); assertEquals(decoded.getAttributeDescription().getAttributeType().getNameOrOID(), "description"); assertTrue(loadMs < PADDING_BUDGET_MS, "padding the decode map to the id " + MAX_LOAD_ID + " took " + loadMs + " ms"); assertTrue(decodeMs < PADDING_BUDGET_MS, "rebuilding the decode map of " + MAX_LOAD_ID + " ids took " + decodeMs + " ms"); } /** The same for the object class maps, which grow through a path of their own. */ @Test public void theDecodeMapIsPaddedToALoadedObjectClassIdInOnePass() throws Exception { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); final long loadStart = System.nanoTime(); assertNotNull( compressedSchema.loadObjectClassesUnder(encodedToken(MAX_LOAD_ID), Arrays.asList("top", "person")), "the highest loadable id is one an encode hands out and its definition was skipped"); final long loadMs = millisSince(loadStart); final long decodeStart = System.nanoTime(); final Map<ObjectClass, String> decoded = compressedSchema.decodeObjectClasses(recordWithToken(encodedToken(MAX_LOAD_ID), false).asReader()); final long decodeMs = millisSince(decodeStart); assertEquals(decoded, objectClasses("top", "person")); assertTrue(loadMs < PADDING_BUDGET_MS, "padding the decode map to the id " + MAX_LOAD_ID + " took " + loadMs + " ms"); assertTrue(decodeMs < PADDING_BUDGET_MS, "rebuilding the decode map of " + MAX_LOAD_ID + " ids took " + decodeMs + " ms"); } /** * A skipped definition leaves nothing behind in the encode map. The load puts the element in the * encode map as well, and a key folding to an id that is live would otherwise leave the skipped * element mapped to that id: an encode would hand out a token that decodes to another definition, * and entries would be written under it - silently, which is worse than the open that fails. */ @Test public void aSkippedDefinitionIsNotLeftInTheEncodeMap() throws Exception { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); // The canonical token of the id 0 is 0x01, and this is that value padded to two bytes. Loaded // before the definition the id 0 belongs to: the order a cursor over a corrupt store reads its // records in is not this test's to choose, and neither order may publish the skipped element. compressedSchema.loadAttributeUnder(new byte[] { 0x00, 0x01 }, "cn"); compressedSchema.loadAttributeAt(0, "description"); final ByteStringBuilder builder = new ByteStringBuilder(); compressedSchema.encodeAttribute(builder, Attributes.create("cn", "a value")); final Attribute decoded = compressedSchema.decodeAttribute(builder.toByteString().asReader()); assertEquals(decoded.getAttributeDescription().getAttributeType().getNameOrOID(), "cn", "an entry was written under a token that decodes to another attribute description"); } /** * A skipped definition still costs the id its key folds to. A key mangled from the canonical one * folds to the id that key addressed, and entries carrying that id are still out there, so * leaving it out of the decode map would let the next registration hand it out again and those * entries would decode as whatever that registration stored. Held as the gap it is - which is * what the reload carries over for the same reason, and what the decode path reports. */ @Test public void aSkippedDefinitionStillCostsTheIdItsKeyNames() throws Exception { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); compressedSchema.loadAttributeAt(0, "sn"); compressedSchema.loadObjectClassesAt(0, Arrays.asList("top", "person")); // The canonical token of the id 2 is 0x03, and this is that value padded to two bytes: what is // lost is the definition of the id 2, an id entries already written carry. compressedSchema.loadAttributeUnder(new byte[] { 0x00, 0x03 }, "cn"); compressedSchema.loadObjectClassesUnder(new byte[] { 0x00, 0x03 }, Arrays.asList("top", "device")); final ByteStringBuilder attributeBuilder = new ByteStringBuilder(); compressedSchema.encodeAttribute(attributeBuilder, Attributes.create("description", "a value")); final ByteStringBuilder objectClassBuilder = new ByteStringBuilder(); compressedSchema.encodeObjectClasses(objectClassBuilder, objectClasses("top", "organizationalUnit")); assertEquals(tokenOf(attributeBuilder.toByteString()), 3, "the id of the skipped definition was handed out again"); assertEquals(tokenOf(objectClassBuilder.toByteString()), 3, "the id of the skipped definition was handed out again"); assertAttributeTokenIsReported(compressedSchema, 2); assertObjectClassTokenIsReported(compressedSchema, 2); } /** * A token past the highest id a definition is loaded back under is never handed out. The decode * map is padded to the ids read out of a storage, so a key accepted at the ceiling leaves the * next registration at an id the next open would refuse: the entry written with it would decode * as nothing once the server is restarted, which is the one thing a registration may not do. */ @Test public void aTokenBeyondTheHighestLoadableIdIsNeverHandedOut() throws Exception { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); compressedSchema.loadAttributeUnder(encodedToken(MAX_LOAD_ID), "description"); compressedSchema.loadObjectClassesUnder(encodedToken(MAX_LOAD_ID), Arrays.asList("top", "person")); try { compressedSchema.encodeAttribute(new ByteStringBuilder(), Attributes.create("cn", "a value")); fail("a token no open would take back should not have been handed out"); } catch (final DirectoryException expected) { assertMessageIs(expected, ERR_COMPRESSEDSCHEMA_NO_TOKEN_LEFT.get(0, 0), "the exhausted token space"); } try { compressedSchema.encodeObjectClasses(new ByteStringBuilder(), objectClasses("top", "device")); fail("a token no open would take back should not have been handed out"); } catch (final DirectoryException expected) { assertMessageIs(expected, ERR_COMPRESSEDSCHEMA_NO_TOKEN_LEFT.get(0, 0), "the exhausted token space"); } assertEquals(compressedSchema.attributeStoreCount, 0, "a token no open would take back was stored"); assertEquals(compressedSchema.objectClassStoreCount, 0, "a token no open would take back was stored"); } /** * Every key an encode writes is one a load takes back. The keys are checked against what this * schema would have written for the id they fold to, so the check has to accept each of the * lengths an id is written in rather than the one byte the small ids of a test fit in. */ @Test public void everyTokenAnEncodeWritesIsLoadedBack() throws Exception { // The ids either side of the byte an encode adds at 0xFF and at 0xFFFF. for (final int id : new int[] { 0, 1, 254, 255, 256, 65534, 65535, 65536 }) { final TestCompressedSchema compressedSchema = new TestCompressedSchema(); assertNotNull(compressedSchema.loadAttributeUnder(encodedToken(id), "description"), "the id " + id + " is one an encode hands out and its definition was skipped"); assertNotNull(compressedSchema.loadObjectClassesUnder(encodedToken(id), Arrays.asList("top", "person")), "the id " + id + " is one an encode hands out and its definition was skipped"); final Attribute decoded = compressedSchema.decodeAttribute(recordWithToken(encodedToken(id), true).asReader()); assertEquals(decoded.getAttributeDescription().getAttributeType().getNameOrOID(), "description", "the definition loaded under the id " + id + " is not the one that token decodes to"); assertEquals(compressedSchema.decodeObjectClasses(recordWithToken(encodedToken(id), false).asReader()), objectClasses("top", "person"), "the definition loaded under the id " + id + " is not the one that token decodes to"); } } /** * What padding a decode map to the highest loadable id may cost. One pass over a map of that size * is milliseconds; a pass per slot is minutes, which is what this separates rather than any * measure of how fast the one pass is. */ private static final long PADDING_BUDGET_MS = 30000; private static long millisSince(final long start) { return TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - start); } /** Keys a compressed schema never hands out, as a corrupt or truncated store holds them. */ private static List<byte[]> unusableTokens() { return Arrays.asList( // Empty, all zero in one byte, and all zero in the four bytes an id is at most written // in: every one of them folds to the id -1, which is not an index of anything. new byte[0], new byte[] { 0x00 }, new byte[] { 0x00, 0x00, 0x00, 0x00 }, // 0xFFFFFFFF, which folds to the id -2. new byte[] { (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF }, // The canonical token of the id 0 padded to two bytes, and past the four bytes an id is // ever written in. Both fold to the id 0, whose definition is live. new byte[] { 0x00, 0x01 }, new byte[] { 0x00, 0x00, 0x00, 0x00, 0x01 }); } /** A record carrying the provided token, with a single value where an attribute is asked for. */ private static ByteString recordWithToken(final byte[] idBytes, final boolean withAValue) { @@ -780,10 +1062,14 @@ return builder.toByteString(); } /** Encodes a token the way CompressedSchema does, one byte being enough for the tests. */ /** * The key a compressed schema writes the definition of the provided id under, through the * encoder production writes it with: a load now takes a definition back only under that exact * key, so a second encoder here would let this suite pass against keys the server rejects. */ private static byte[] encodedToken(final int id) { return new byte[] { (byte) ((id + 1) & 0xFF) }; return CompressedSchema.encodeId(id); } /** Decodes a token the way CompressedSchema does. */ opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/PersistentCompressedSchemaTest.java
@@ -21,6 +21,8 @@ import static org.mockito.Mockito.mock; import static org.testng.Assert.fail; import org.forgerock.opendj.io.ASN1; import org.forgerock.opendj.io.ASN1Writer; import org.forgerock.opendj.ldap.ByteSequence; import org.forgerock.opendj.ldap.ByteString; import org.forgerock.opendj.ldap.ByteStringBuilder; @@ -246,6 +248,46 @@ } } /** * A record stored under a key no compressed schema hands out must cost the definition it carries * and nothing else: the backend still opens, and the definitions stored under the keys this * schema did write are still there (issue #897). * <p> * The load path folds whatever key a record is stored under into an id and hands it straight to * the decode map, so an all-zero key - what a truncated record leaves - reached it as the index * -1 and left the open as an IndexOutOfBoundsException, while a key folding to the largest id * four bytes address left it padding the map two billion slots, one at a time, with nothing in * the log to say what the open was waiting for. */ @Test public void aDefinitionStoredUnderAnUnusableKeyDoesNotStopTheOpen() throws Exception { final ByteString encoded = encode(open("backendA", AccessMode.READ_WRITE), "cn"); // Read before the definition of "cn", whose key is 0x01: a cursor walks the keys in order, so // the open used to end on this one before it reached anything else. storeDefinitionUnder(ownTree("backendA", AD), ByteString.wrap(new byte[] { 0x00 }), "description"); storeDefinitionUnder(ownTree("backendA", AD), ByteString.wrap(new byte[] { 0x7F, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF }), "sn"); final PersistentCompressedSchema reopened = open("backendA", AccessMode.READ_WRITE); assertThat(decode(reopened, encoded)).isEqualTo("cn"); // and a definition that was skipped is registered afresh when it is next encoded, rather than // taken from the key it was stored under: it gets a token this schema hands out and stores. assertThat(decode(reopened, encode(reopened, "description"))).isEqualTo("description"); } /** Writes an attribute description definition under a key of this test's choosing. */ private void storeDefinitionUnder(TreeName treeName, ByteString key, String attributeName) throws Exception { final ByteStringBuilder definition = new ByteStringBuilder(); final ASN1Writer writer = ASN1.getWriter(definition); writer.writeStartSequence(); writer.writeOctetString(attributeName); writer.writeEndSequence(); txn.put(treeName, key, definition); } private PersistentCompressedSchema open(String backendId, AccessMode accessMode) throws Exception { return new PersistentCompressedSchema(serverContext, backendId, storage, txn, accessMode);
