001/*
002 * The contents of this file are subject to the terms of the Common Development and
003 * Distribution License (the License). You may not use this file except in compliance with the
004 * License.
005 *
006 * You can obtain a copy of the License at legal/CDDLv1.0.txt. See the License for the
007 * specific language governing permission and limitations under the License.
008 *
009 * When distributing Covered Software, include this CDDL Header Notice in each file and include
010 * the License file at legal/CDDLv1.0.txt. If applicable, add the following below the CDDL
011 * Header, with the fields enclosed by brackets [] replaced by your own identifying
012 * information: "Portions Copyright [year] [name of copyright owner]".
013 *
014 * Copyright 2009 Sun Microsystems, Inc.
015 * Portions Copyright 2013-2017 ForgeRock AS.
016 */
017package org.opends.server.api;
018
019import static org.opends.messages.CoreMessages.*;
020
021import java.util.AbstractMap.SimpleImmutableEntry;
022import java.util.Collection;
023import java.util.Collections;
024import java.util.Iterator;
025import java.util.LinkedHashMap;
026import java.util.LinkedHashSet;
027import java.util.List;
028import java.util.Map;
029import java.util.Map.Entry;
030import java.util.Set;
031import java.util.concurrent.ConcurrentHashMap;
032import java.util.concurrent.CopyOnWriteArrayList;
033
034import net.jcip.annotations.GuardedBy;
035
036import org.forgerock.opendj.ldap.AttributeDescription;
037import org.forgerock.opendj.ldap.ByteSequenceReader;
038import org.forgerock.opendj.ldap.ByteString;
039import org.forgerock.opendj.ldap.ByteStringBuilder;
040import org.forgerock.opendj.ldap.schema.AttributeType;
041import org.forgerock.opendj.ldap.schema.ObjectClass;
042import org.forgerock.opendj.ldap.schema.Schema;
043import org.opends.server.core.DirectoryServer;
044import org.opends.server.core.ServerContext;
045import org.opends.server.types.Attribute;
046import org.opends.server.types.AttributeBuilder;
047import org.opends.server.types.Attributes;
048import org.opends.server.types.DirectoryException;
049
050/**
051 * This class provides a utility for interacting with compressed representations
052 * of schema elements. The default implementation does not persist encoded
053 * attributes and object classes.
054 */
055@org.opends.server.types.PublicAPI(
056    stability = org.opends.server.types.StabilityLevel.UNCOMMITTED,
057    mayInstantiate = false,
058    mayExtend = true,
059    mayInvoke = false)
060public class CompressedSchema
061{
062  /** Encloses all the encode and decode mappings for attribute and object classes. */
063  private static final class Mappings
064  {
065    /** Schema used to build the compressed information. */
066    private final Schema schema;
067
068    /** Maps encoded representation's ID to its attribute description (the List's index is the ID). */
069    private final List<AttributeDescription> adDecodeMap = new CopyOnWriteArrayList<>();
070    /** Maps attribute description to its encoded representation's ID. */
071    private final Map<AttributeDescription, Integer> adEncodeMap;
072    /** Maps encoded representation's ID to its object class (the List's index is the ID). */
073    private final List<Map<ObjectClass, String>> ocDecodeMap = new CopyOnWriteArrayList<>();
074    /** Maps object class to its encoded representation's ID. */
075    private final Map<Map<ObjectClass, String>, Integer> ocEncodeMap;
076
077    private Mappings()
078    {
079      this.schema = null;
080      this.adEncodeMap = new ConcurrentHashMap<>();
081      this.ocEncodeMap = new ConcurrentHashMap<>();
082    }
083
084    private Mappings(final Schema schema, int adEncodeMapSize, int ocEncodeMapSize)
085    {
086      this.schema = schema;
087      this.adEncodeMap = new ConcurrentHashMap<>(adEncodeMapSize);
088      this.ocEncodeMap = new ConcurrentHashMap<>(ocEncodeMapSize);
089    }
090  }
091
092  private final ServerContext serverContext;
093  /** Lock to update the mappings. */
094  private final Object mappingsLock = new Object();
095  /**
096   * The compressed schema shared lock was found to be very hot (see OPENDJ-4027). Therefore use lock-free volatile
097   * access for fast-path where possible and only resort to locking when absolutely necessary.
098   */
099  @GuardedBy("mappingsLock")
100  private volatile Mappings mappings = new Mappings();
101
102  /**
103   * Creates a new empty instance of this compressed schema.
104   *
105   * @param serverContext
106   *            The server context.
107   */
108  public CompressedSchema(ServerContext serverContext)
109  {
110    this.serverContext = serverContext;
111  }
112
113  private Mappings getMappings()
114  {
115    return mappings;
116  }
117
118  private Mappings reloadMappingsIfSchemaChanged()
119  {
120    final Mappings currentMappings = mappings;
121    Schema currentSchema = serverContext.getSchemaNG();
122    if (currentMappings.schema == currentSchema)
123    {
124      return currentMappings;
125    }
126
127    synchronized (mappingsLock)
128    {
129      currentSchema = serverContext.getSchemaNG();
130      if (mappings.schema == currentSchema)
131      {
132        return mappings;
133      }
134
135      // build new maps from existing ones
136      final Mappings newMappings = new Mappings(currentSchema, mappings.adEncodeMap.size(),
137                                                mappings.ocEncodeMap.size());
138      reloadAttributeTypeMaps(mappings, newMappings);
139      reloadObjectClassesMap(mappings, newMappings);
140      mappings = newMappings;
141      return mappings;
142    }
143  }
144
145  /**
146   * Reload the attribute types maps. This should be called when schema has changed, because some
147   * types may be out dated.
148   */
149  private void reloadAttributeTypeMaps(Mappings mappings, Mappings newMappings)
150  {
151    for (Entry<AttributeDescription, Integer> entry : mappings.adEncodeMap.entrySet())
152    {
153      AttributeDescription ad = entry.getKey();
154      Integer id = entry.getValue();
155      loadAttributeToMaps(id, ad.getAttributeType().getNameOrOID(), ad.getOptions(), newMappings);
156    }
157  }
158
159  /**
160   * Reload the object classes maps. This should be called when schema has changed, because some
161   * classes may be out dated.
162   */
163  private void reloadObjectClassesMap(Mappings mappings, Mappings newMappings)
164  {
165    for (Entry<Map<ObjectClass, String>, Integer> entry : mappings.ocEncodeMap.entrySet())
166    {
167      Map<ObjectClass, String> ocMap = entry.getKey();
168      Integer id = entry.getValue();
169      loadObjectClassesToMaps(id, ocMap.values(), newMappings, false);
170    }
171  }
172
173  /**
174   * Decodes the contents of the provided array as an attribute at the current
175   * position.
176   *
177   * @param reader
178   *          The byte string reader containing the encoded entry.
179   * @return The decoded attribute.
180   * @throws DirectoryException
181   *           If the attribute could not be decoded properly for some reason.
182   */
183  public final Attribute decodeAttribute(final ByteSequenceReader reader)
184      throws DirectoryException
185  {
186    // First decode the encoded attribute description id.
187    final int adId = decodeId(reader);
188
189    // Before returning the attribute, make sure that the attribute type is not stale.
190    final Mappings mappings = reloadMappingsIfSchemaChanged();
191    final AttributeDescription ad = mappings.adDecodeMap.get(adId);
192    if (ad == null)
193    {
194      throw new DirectoryException(DirectoryServer.getServerErrorResultCode(),
195          ERR_COMPRESSEDSCHEMA_UNRECOGNIZED_AD_TOKEN.get(adId));
196    }
197
198    AttributeType attrType = ad.getAttributeType();
199
200    // Determine the number of values for the attribute.
201    final int numValues = reader.readBERLength();
202
203    // For the common case of a single value with no options, generate less garbage.
204    if (numValues == 1 && !ad.hasOptions())
205    {
206      return Attributes.create(attrType, readValue(reader));
207    }
208    else
209    {
210      // Read the appropriate number of values.
211      final AttributeBuilder builder = new AttributeBuilder(attrType);
212      builder.setOptions(ad.getOptions());
213      for (int i = 0; i < numValues; i++)
214      {
215        builder.add(readValue(reader));
216      }
217      return builder.toAttribute();
218    }
219  }
220
221  private ByteString readValue(final ByteSequenceReader reader)
222  {
223    return reader.readByteSequence(reader.readBERLength()).toByteString();
224  }
225
226  /**
227   * Decodes an object class set from the provided byte string.
228   *
229   * @param reader
230   *          The byte string reader containing the object class set identifier.
231   * @return The decoded object class set.
232   * @throws DirectoryException
233   *           If the provided byte string reader cannot be decoded as an object
234   *           class set.
235   */
236  public final Map<ObjectClass, String> decodeObjectClasses(
237      final ByteSequenceReader reader) throws DirectoryException
238  {
239    // First decode the encoded object class id.
240    final int ocId = decodeId(reader);
241
242    // Before returning the object classes, make sure that none of them are stale.
243    final Mappings mappings = reloadMappingsIfSchemaChanged();
244    Map<ObjectClass, String> ocMap = mappings.ocDecodeMap.get(ocId);
245    if (ocMap == null)
246    {
247      throw new DirectoryException(DirectoryServer.getServerErrorResultCode(),
248          ERR_COMPRESSEDSCHEMA_UNKNOWN_OC_TOKEN.get(ocId));
249    }
250    return ocMap;
251  }
252
253  /**
254   * Encodes the information in the provided attribute to a byte array.
255   *
256   * @param builder
257   *          The buffer to encode the attribute to.
258   * @param attribute
259   *          The attribute to be encoded.
260   * @throws DirectoryException
261   *           If a problem occurs while attempting to determine the appropriate
262   *           identifier.
263   */
264  public final void encodeAttribute(final ByteStringBuilder builder,
265      final Attribute attribute) throws DirectoryException
266  {
267    // Re-use or allocate a new ID.
268    int id = getAttributeId(attribute.getAttributeDescription());
269
270    // Encode the attribute.
271    final byte[] idBytes = encodeId(id);
272    builder.appendBERLength(idBytes.length);
273    builder.appendBytes(idBytes);
274    builder.appendBERLength(attribute.size());
275    for (final ByteString v : attribute)
276    {
277      builder.appendBERLength(v.length());
278      builder.appendBytes(v);
279    }
280  }
281
282  private int getAttributeId(final AttributeDescription ad) throws DirectoryException
283  {
284    Integer id = mappings.adEncodeMap.get(ad);
285    if (id != null)
286    {
287      return id;
288    }
289
290    synchronized (mappingsLock)
291    {
292      id = mappings.adEncodeMap.get(ad);
293      if (id != null)
294      {
295        return id;
296      }
297
298      id = mappings.adDecodeMap.size();
299      mappings.adDecodeMap.add(ad);
300      mappings.adEncodeMap.put(ad, id);
301      storeAttribute(encodeId(id), ad.getAttributeType().getNameOrOID(), ad.getOptions());
302      return id;
303    }
304  }
305
306  /**
307   * Encodes the provided set of object classes to a byte array. If the same set
308   * had been previously encoded, then the cached value will be used. Otherwise,
309   * a new value will be created.
310   *
311   * @param builder
312   *          The buffer to encode the object classes to.
313   * @param objectClasses
314   *          The set of object classes for which to retrieve the corresponding
315   *          byte array token.
316   * @throws DirectoryException
317   *           If a problem occurs while attempting to determine the appropriate
318   *           identifier.
319   */
320  public final void encodeObjectClasses(final ByteStringBuilder builder,
321      final Map<ObjectClass, String> objectClasses) throws DirectoryException
322  {
323    // Re-use or allocate a new ID.
324    int id = getObjectClassId(objectClasses);
325
326    // Encode the object classes.
327    final byte[] idBytes = encodeId(id);
328    builder.appendBERLength(idBytes.length);
329    builder.appendBytes(idBytes);
330  }
331
332  private int getObjectClassId(final Map<ObjectClass, String> objectClasses) throws DirectoryException
333  {
334    Integer id = mappings.ocEncodeMap.get(objectClasses);
335    if (id != null)
336    {
337      return id;
338    }
339
340    synchronized (mappingsLock)
341    {
342      id = mappings.ocEncodeMap.get(objectClasses);
343      if (id != null)
344      {
345        return id;
346      }
347
348      id = mappings.ocDecodeMap.size();
349      mappings.ocDecodeMap.add(objectClasses);
350      mappings.ocEncodeMap.put(objectClasses, id);
351      storeObjectClasses(encodeId(id), objectClasses.values());
352      return id;
353    }
354  }
355
356  /**
357   * Returns a view of the encoded attributes in this compressed schema which can be used for saving
358   * the entire content to disk.
359   * <p>
360   * The iterator returned by this method is not thread safe.
361   *
362   * @return A view of the encoded attributes in this compressed schema.
363   */
364  protected final Iterable<Entry<byte[], Entry<String, Iterable<String>>>> getAllAttributes()
365  {
366    return new Iterable<Entry<byte[], Entry<String, Iterable<String>>>>()
367    {
368      @Override
369      public Iterator<Entry<byte[], Entry<String, Iterable<String>>>> iterator()
370      {
371        return new Iterator<Entry<byte[], Entry<String, Iterable<String>>>>()
372        {
373          private int id;
374          private List<AttributeDescription> adDecodeMap = getMappings().adDecodeMap;
375
376          @Override
377          public boolean hasNext()
378          {
379            return id < adDecodeMap.size();
380          }
381
382          @Override
383          public Entry<byte[], Entry<String, Iterable<String>>> next()
384          {
385            final byte[] encodedAttribute = encodeId(id);
386            final AttributeDescription ad = adDecodeMap.get(id++);
387            return new SimpleImmutableEntry<byte[], Entry<String, Iterable<String>>>(
388                encodedAttribute,
389                new SimpleImmutableEntry<String, Iterable<String>>(
390                    ad.getAttributeType().getNameOrOID(), ad.getOptions()));
391          }
392
393          @Override
394          public void remove()
395          {
396            throw new UnsupportedOperationException();
397          }
398        };
399      }
400    };
401  }
402
403  /**
404   * Returns a view of the encoded object classes in this compressed schema which can be used for
405   * saving the entire content to disk.
406   * <p>
407   * The iterator returned by this method is not thread safe.
408   *
409   * @return A view of the encoded object classes in this compressed schema.
410   */
411  protected final Iterable<Entry<byte[], Collection<String>>> getAllObjectClasses()
412  {
413    return new Iterable<Entry<byte[], Collection<String>>>()
414    {
415      @Override
416      public Iterator<Entry<byte[], Collection<String>>> iterator()
417      {
418        return new Iterator<Map.Entry<byte[], Collection<String>>>()
419        {
420          private int id;
421          private final List<Map<ObjectClass, String>> ocDecodeMap = getMappings().ocDecodeMap;
422
423          @Override
424          public boolean hasNext()
425          {
426            return id < ocDecodeMap.size();
427          }
428
429          @Override
430          public Entry<byte[], Collection<String>> next()
431          {
432            final byte[] encodedObjectClasses = encodeId(id);
433            final Map<ObjectClass, String> ocMap = ocDecodeMap.get(id++);
434            return new SimpleImmutableEntry<>(encodedObjectClasses, ocMap.values());
435          }
436
437          @Override
438          public void remove()
439          {
440            throw new UnsupportedOperationException();
441          }
442        };
443      }
444    };
445  }
446
447  /**
448   * Loads an encoded attribute into this compressed schema. This method may
449   * called by implementations during initialization when loading content from
450   * disk.
451   *
452   * @param encodedAttribute
453   *          The encoded attribute description.
454   * @param attributeName
455   *          The user provided attribute type name.
456   * @param attributeOptions
457   *          The non-null but possibly empty set of attribute options.
458   * @return The attribute type description.
459   */
460  protected final AttributeDescription loadAttribute(
461      final byte[] encodedAttribute, final String attributeName,
462      final Collection<String> attributeOptions)
463  {
464    final int id = decodeId(encodedAttribute);
465    return loadAttributeToMaps(id, attributeName, attributeOptions, getMappings());
466  }
467
468  /**
469   * Loads an attribute into provided encode and decode maps, given its id, name, and options.
470   *
471   * @param id
472   *          the id computed on the attribute.
473   * @param attributeName
474   *          The user provided attribute type name.
475   * @param attributeOptions
476   *          The non-null but possibly empty set of attribute options.
477   * @param mappings
478   *          attribute description encodeMap and decodeMap maps id to entry
479   * @return The attribute type description.
480   */
481  private AttributeDescription loadAttributeToMaps(final int id, final String attributeName,
482      final Iterable<String> attributeOptions, final Mappings mappings)
483  {
484    final AttributeType type = DirectoryServer.getSchema().getAttributeType(attributeName);
485    final Set<String> options = getOptions(attributeOptions);
486    final AttributeDescription ad = AttributeDescription.create(type, options);
487    synchronized (mappingsLock)
488    {
489      mappings.adEncodeMap.put(ad, id);
490      if (id < mappings.adDecodeMap.size())
491      {
492        mappings.adDecodeMap.set(id, ad);
493      }
494      else
495      {
496        // Grow the decode array.
497        while (id > mappings.adDecodeMap.size())
498        {
499          mappings.adDecodeMap.add(null);
500        }
501        mappings.adDecodeMap.add(ad);
502      }
503      return ad;
504    }
505  }
506
507  private Set<String> getOptions(final Iterable<String> attributeOptions)
508  {
509    Iterator<String> it = attributeOptions.iterator();
510    if (!it.hasNext())
511    {
512      return Collections.emptySet();
513    }
514    String firstOption = it.next();
515    if (!it.hasNext())
516    {
517      return Collections.singleton(firstOption);
518    }
519    LinkedHashSet<String> results = new LinkedHashSet<>();
520    results.add(firstOption);
521    while (it.hasNext())
522    {
523      results.add(it.next());
524    }
525    return results;
526  }
527
528  /**
529   * Loads an encoded object class into this compressed schema. This method may
530   * called by implementations during initialization when loading content from
531   * disk.
532   *
533   * @param encodedObjectClasses
534   *          The encoded object classes.
535   * @param objectClassNames
536   *          The user provided set of object class names.
537   * @return The object class set.
538   */
539  protected final Map<ObjectClass, String> loadObjectClasses(
540      final byte[] encodedObjectClasses,
541      final Collection<String> objectClassNames)
542  {
543    final int id = decodeId(encodedObjectClasses);
544    return loadObjectClassesToMaps(id, objectClassNames, mappings, true);
545  }
546
547  /**
548   * Loads a set of object classes into provided encode and decode maps, given the id and set of
549   * names.
550   *
551   * @param id
552   *          the id computed on the object classes set.
553   * @param objectClassNames
554   *          The user provided set of object class names.
555   * @param mappings
556   *          .ocEncodeMap maps id to entry
557   * @param mappings
558   *          .ocDecodeMap maps entry to id
559   * @param sync
560   *          indicates if update of maps should be synchronized
561   * @return The object class set.
562   */
563  private final Map<ObjectClass, String> loadObjectClassesToMaps(int id, final Collection<String> objectClassNames,
564      Mappings mappings, boolean sync)
565  {
566    final LinkedHashMap<ObjectClass, String> ocMap = new LinkedHashMap<>(objectClassNames.size());
567    for (final String name : objectClassNames)
568    {
569      ocMap.put(DirectoryServer.getSchema().getObjectClass(name), name);
570    }
571    if (sync)
572    {
573      synchronized (mappingsLock)
574      {
575        updateObjectClassesMaps(id, mappings, ocMap);
576      }
577    }
578    else
579    {
580      updateObjectClassesMaps(id, mappings, ocMap);
581    }
582    return ocMap;
583  }
584
585  private void updateObjectClassesMaps(int id, Mappings mappings, LinkedHashMap<ObjectClass, String> ocMap)
586  {
587    mappings.ocEncodeMap.put(ocMap, id);
588    if (id < mappings.ocDecodeMap.size())
589    {
590      mappings.ocDecodeMap.set(id, ocMap);
591    }
592    else
593    {
594      // Grow the decode array.
595      while (id > mappings.ocDecodeMap.size())
596      {
597        mappings.ocDecodeMap.add(null);
598      }
599      mappings.ocDecodeMap.add(ocMap);
600    }
601  }
602
603  /**
604   * Persists the provided encoded attribute. The default implementation is to
605   * do nothing. Calls to this method are synchronized, so implementations can
606   * assume that this method is not being called by other threads. Note that
607   * this method is not thread-safe with respect to
608   * {@link #storeObjectClasses(byte[], Collection)}.
609   *
610   * @param encodedAttribute
611   *          The encoded attribute description.
612   * @param attributeName
613   *          The user provided attribute type name.
614   * @param attributeOptions
615   *          The non-null but possibly empty set of attribute options.
616   * @throws DirectoryException
617   *           If an error occurred while persisting the encoded attribute.
618   */
619  protected void storeAttribute(final byte[] encodedAttribute,
620      final String attributeName, final Iterable<String> attributeOptions)
621      throws DirectoryException
622  {
623    // Do nothing by default.
624  }
625
626  /**
627   * Persists the provided encoded object classes. The default implementation is
628   * to do nothing. Calls to this method are synchronized, so implementations
629   * can assume that this method is not being called by other threads. Note that
630   * this method is not thread-safe with respect to
631   * {@link #storeAttribute(byte[], String, Iterable)}.
632   *
633   * @param encodedObjectClasses
634   *          The encoded object classes.
635   * @param objectClassNames
636   *          The user provided set of object class names.
637   * @throws DirectoryException
638   *           If an error occurred while persisting the encoded object classes.
639   */
640  protected void storeObjectClasses(final byte[] encodedObjectClasses,
641      final Collection<String> objectClassNames) throws DirectoryException
642  {
643    // Do nothing by default.
644  }
645
646  /**
647   * Decodes the provided encoded schema element ID.
648   *
649   * @param idBytes
650   *          The encoded schema element ID.
651   * @return The schema element ID.
652   */
653  private int decodeId(final byte[] idBytes)
654  {
655    int id = 0;
656    for (final byte b : idBytes)
657    {
658      id <<= 8;
659      id |= b & 0xFF;
660    }
661    return id - 1; // Subtract 1 to compensate for old behavior.
662  }
663
664  private int decodeId(final ByteSequenceReader reader)
665  {
666    final int length = reader.readBERLength();
667    final byte[] idBytes = new byte[length];
668    reader.readBytes(idBytes);
669    return decodeId(idBytes);
670  }
671
672  /**
673   * Encodes the provided schema element ID.
674   *
675   * @param id
676   *          The schema element ID.
677   * @return The encoded schema element ID.
678   */
679  private byte[] encodeId(final int id)
680  {
681    final int value = id + 1; // Add 1 to compensate for old behavior.
682    final byte[] idBytes;
683    if (value <= 0xFF)
684    {
685      idBytes = new byte[1];
686      idBytes[0] = (byte) (value & 0xFF);
687    }
688    else if (value <= 0xFFFF)
689    {
690      idBytes = new byte[2];
691      idBytes[0] = (byte) ((value >> 8) & 0xFF);
692      idBytes[1] = (byte) (value & 0xFF);
693    }
694    else if (value <= 0xFFFFFF)
695    {
696      idBytes = new byte[3];
697      idBytes[0] = (byte) ((value >> 16) & 0xFF);
698      idBytes[1] = (byte) ((value >> 8) & 0xFF);
699      idBytes[2] = (byte) (value & 0xFF);
700    }
701    else
702    {
703      idBytes = new byte[4];
704      idBytes[0] = (byte) ((value >> 24) & 0xFF);
705      idBytes[1] = (byte) ((value >> 16) & 0xFF);
706      idBytes[2] = (byte) ((value >> 8) & 0xFF);
707      idBytes[3] = (byte) (value & 0xFF);
708    }
709    return idBytes;
710  }
711}