Package com.fasterxml.jackson.core.sym
Class ByteQuadsCanonicalizer
- java.lang.Object
-
- com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer
-
public final class ByteQuadsCanonicalizer extends java.lang.ObjectReplacement forBytesToNameCanonicalizerwhich aims at more localized memory access due to flattening of name quad data. Performance improvement modest for simple JSON document data binding (maybe 3%), but should help more for larger symbol tables, or for binary formats like Smile.Hash area is divided into 4 sections:
- Primary area (1/2 of total size), direct match from hash (LSB)
- Secondary area (1/4 of total size), match from
hash (LSB) >> 1 - Tertiary area (1/8 of total size), match from
hash (LSB) >> 2 - Spill-over area (remaining 1/8) with linear scan, insertion order
ints, where 1 - 3 ints contain 1 - 12 UTF-8 encoded bytes of name (null-padded), and last int is offset in_namesthat contains actual name Strings.- Since:
- 2.6
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static classByteQuadsCanonicalizer.TableInfoImmutable value class used for sharing information as efficiently as possible, by only require synchronization of reference manipulation but not access to contents.
-
Field Summary
Fields Modifier and Type Field Description protected int_countTotal number of Strings in the symbol table; only used for child tables.protected boolean_failOnDoSFlag that indicates whether we should throw an exception if enough hash collisions are detected (true); or just worked around (false).protected int[]_hashAreaPrimary hash information area: consists of2 * _hashSizeentries of 16 bytes (4 ints), arranged in a cascading lookup structure (details of which may be tweaked depending on expected rates of collisions).protected boolean_hashSharedFlag that indicates whether underlying data structures for the main hash area are shared or not.protected int_hashSizeNumber of slots for primary entries within_hashArea; which is at most1/8of actual size of the underlying array (4-int slots, primary covers only half of the area; plus, additional area for longer symbols after hash area).protected InternCache_internerEntity that knows how tointernStrings, if needed, ornullif no interning is wanted.protected int_longNameOffsetOffset within_hashAreathat follows main slots and contains quads for longer names (13 bytes or longer), and points to the first available int that may be used for appending quads of the next long name.protected java.lang.String[]_namesArray that containsStringinstances matching entries in_hashArea.protected ByteQuadsCanonicalizer_parentReference to the root symbol table, for child tables, so that they can merge table information back as necessary.protected int_secondaryStartOffset within_hashAreawhere secondary entries startprotected int_seedSeed value we use as the base to make hash codes non-static between different runs, but still stable for lifetime of a single symbol table instance.protected int_spilloverEndPointer to the offset within spill-over area where there is room for more spilled over entries (if any).protected java.util.concurrent.atomic.AtomicReference<ByteQuadsCanonicalizer.TableInfo>_tableInfoMember that is only used by the root table instance: root passes immutable state info child instances, and children may return new state if they add entries to the table.protected int_tertiaryShiftConstant that determines size of buckets for tertiary entries:1 << _tertiaryShiftis the size, and shift value is also used for translating from primary offset into tertiary bucket (shift right by4 + _tertiaryShift).protected int_tertiaryStartOffset within_hashAreawhere tertiary entries startprivate static intDEFAULT_T_SIZEInitial size of the primary hash area.protected static intMAX_ENTRIES_FOR_REUSELet's only share reasonably sized symbol tables.private static intMAX_T_SIZELet's not expand symbol tables past some maximum size; with unique (~= random) names.private static intMIN_HASH_SIZENo point in trying to construct tiny tables, just need to resize soon.private static intMULTprivate static intMULT2private static intMULT3
-
Constructor Summary
Constructors Modifier Constructor Description privateByteQuadsCanonicalizer(int sz, int seed)Constructor used for creating per-TokenStreamFactory"root" symbol tables: ones used for merging and sharing common symbolsprivateByteQuadsCanonicalizer(ByteQuadsCanonicalizer.TableInfo state)Alternate constructor used in cases where a "placeholder" child instance is needed when symbol table is not really used, but caller needs a non-null placeholder to keep code functioning with minimal awareness of distinction (all lookups fail to match any name without error; add methods should NOT be called).privateByteQuadsCanonicalizer(ByteQuadsCanonicalizer parent, int seed, ByteQuadsCanonicalizer.TableInfo state, boolean intern, boolean failOnDoS)Constructor used when creating a child instance
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private int_appendLongName(int[] quads, int qlen)private int_calcOffset(int hash)(package private) static int_calcTertiaryShift(int primarySlots)private boolean_checkNeedForRehash()private int_findOffsetForAdd(int hash)Method called to find the location within hash table to add a new symbol in.private java.lang.String_findSecondary(int origOffset, int q1)private java.lang.String_findSecondary(int origOffset, int q1, int q2)private java.lang.String_findSecondary(int origOffset, int hash, int[] q, int qlen)private java.lang.String_findSecondary(int origOffset, int q1, int q2, int q3)protected void_reportTooManyCollisions()private int_resizeAndFindOffsetForAdd(int hash)private int_spilloverStart()Helper method that calculates start of the spillover areaprivate boolean_verifyLongName(int[] q, int qlen, int spillOffset)private boolean_verifyLongName2(int[] q, int qlen, int spillOffset)private void_verifySharing()java.lang.StringaddName(java.lang.String name, int q1)java.lang.StringaddName(java.lang.String name, int[] q, int qlen)java.lang.StringaddName(java.lang.String name, int q1, int q2)java.lang.StringaddName(java.lang.String name, int q1, int q2, int q3)intbucketCount()intcalcHash(int q1)intcalcHash(int[] q, int qlen)intcalcHash(int q1, int q2)intcalcHash(int q1, int q2, int q3)static ByteQuadsCanonicalizercreateRoot()Factory method to call to create a symbol table instance with a randomized seed value.protected static ByteQuadsCanonicalizercreateRoot(int seed)java.lang.StringfindName(int q1)java.lang.StringfindName(int[] q, int qlen)java.lang.StringfindName(int q1, int q2)java.lang.StringfindName(int q1, int q2, int q3)inthashSeed()booleanisCanonicalizing()ByteQuadsCanonicalizermakeChild(int flags)Factory method used to create actual symbol table instance to use for parsing.ByteQuadsCanonicalizermakeChildOrPlaceholder(int flags)Method similar tomakeChild(int)but one that only creates real instance ofJsonFactory.Feature.CANONICALIZE_FIELD_NAMESis enabled: otherwise a "bogus" instance is created.booleanmaybeDirty()Method called to check to quickly see if a child symbol table may have gotten additional entries.private voidmergeChild(ByteQuadsCanonicalizer.TableInfo childState)(package private) static intmultiplyByFourFifths(int number)private voidnukeSymbols(boolean fill)Helper method called to empty all shared symbols, but to leave arrays allocatedintprimaryCount()Method mostly needed by unit tests; calculates number of entries that are in the primary slot set.private voidrehash()voidrelease()Method called by the using code to indicate it is done with this instance.intsecondaryCount()Method mostly needed by unit tests; calculates number of entries in secondary bucketsintsize()intspilloverCount()Method mostly needed by unit tests; calculates number of entries in shared spill-over areainttertiaryCount()Method mostly needed by unit tests; calculates number of entries in tertiary bucketsjava.lang.StringtoString()inttotalCount()
-
-
-
Field Detail
-
DEFAULT_T_SIZE
private static final int DEFAULT_T_SIZE
Initial size of the primary hash area. Each entry consumes 4 ints (16 bytes), and secondary area is same as primary; so default size will use 2kB of memory (plus 64x4 or 64x8 (256/512 bytes) for references to Strings, and Strings themselves).- See Also:
- Constant Field Values
-
MAX_T_SIZE
private static final int MAX_T_SIZE
Let's not expand symbol tables past some maximum size; with unique (~= random) names. Size is in- See Also:
- Constant Field Values
-
MIN_HASH_SIZE
private static final int MIN_HASH_SIZE
No point in trying to construct tiny tables, just need to resize soon.- See Also:
- Constant Field Values
-
MAX_ENTRIES_FOR_REUSE
protected static final int MAX_ENTRIES_FOR_REUSE
Let's only share reasonably sized symbol tables. Max size set to 3/4 of 8k; this corresponds to 256k main hash index. This should allow for enough distinct names for almost any case, while preventing ballooning for cases where names are unique (or close thereof).- See Also:
- Constant Field Values
-
_parent
protected final ByteQuadsCanonicalizer _parent
Reference to the root symbol table, for child tables, so that they can merge table information back as necessary.
-
_tableInfo
protected final java.util.concurrent.atomic.AtomicReference<ByteQuadsCanonicalizer.TableInfo> _tableInfo
Member that is only used by the root table instance: root passes immutable state info child instances, and children may return new state if they add entries to the table. Child tables do NOT use the reference.
-
_seed
protected final int _seed
Seed value we use as the base to make hash codes non-static between different runs, but still stable for lifetime of a single symbol table instance. This is done for security reasons, to avoid potential DoS attack via hash collisions.
-
_interner
protected final InternCache _interner
Entity that knows how tointernStrings, if needed, ornullif no interning is wanted.- Since:
- 2.16
-
_failOnDoS
protected final boolean _failOnDoS
Flag that indicates whether we should throw an exception if enough hash collisions are detected (true); or just worked around (false).- Since:
- 2.4
-
_hashArea
protected int[] _hashArea
Primary hash information area: consists of2 * _hashSizeentries of 16 bytes (4 ints), arranged in a cascading lookup structure (details of which may be tweaked depending on expected rates of collisions).
-
_hashSize
protected int _hashSize
Number of slots for primary entries within_hashArea; which is at most1/8of actual size of the underlying array (4-int slots, primary covers only half of the area; plus, additional area for longer symbols after hash area).
-
_secondaryStart
protected int _secondaryStart
Offset within_hashAreawhere secondary entries start
-
_tertiaryStart
protected int _tertiaryStart
Offset within_hashAreawhere tertiary entries start
-
_tertiaryShift
protected int _tertiaryShift
Constant that determines size of buckets for tertiary entries:1 << _tertiaryShiftis the size, and shift value is also used for translating from primary offset into tertiary bucket (shift right by4 + _tertiaryShift).Default value is 2, for buckets of 4 slots; grows bigger with bigger table sizes.
-
_count
protected int _count
Total number of Strings in the symbol table; only used for child tables.
-
_names
protected java.lang.String[] _names
-
_spilloverEnd
protected int _spilloverEnd
Pointer to the offset within spill-over area where there is room for more spilled over entries (if any). Spill over area is within fixed-size portion of_hashArea.
-
_longNameOffset
protected int _longNameOffset
-
_hashShared
protected boolean _hashShared
Flag that indicates whether underlying data structures for the main hash area are shared or not. If they are, then they need to be handled in copy-on-write way, i.e. if they need to be modified, a copy needs to be made first; at this point it will not be shared any more, and can be modified.This flag needs to be checked both when adding new main entries, and when adding new collision list queues (i.e. creating a new collision list head entry)
-
MULT
private static final int MULT
- See Also:
- Constant Field Values
-
MULT2
private static final int MULT2
- See Also:
- Constant Field Values
-
MULT3
private static final int MULT3
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
ByteQuadsCanonicalizer
private ByteQuadsCanonicalizer(int sz, int seed)Constructor used for creating per-TokenStreamFactory"root" symbol tables: ones used for merging and sharing common symbols- Parameters:
sz- Initial primary hash area sizeseed- Random seed valued used to make it more difficult to cause collisions (used for collision-based DoS attacks).
-
ByteQuadsCanonicalizer
private ByteQuadsCanonicalizer(ByteQuadsCanonicalizer parent, int seed, ByteQuadsCanonicalizer.TableInfo state, boolean intern, boolean failOnDoS)
Constructor used when creating a child instance
-
ByteQuadsCanonicalizer
private ByteQuadsCanonicalizer(ByteQuadsCanonicalizer.TableInfo state)
Alternate constructor used in cases where a "placeholder" child instance is needed when symbol table is not really used, but caller needs a non-null placeholder to keep code functioning with minimal awareness of distinction (all lookups fail to match any name without error; add methods should NOT be called).- Since:
- 2.13
-
-
Method Detail
-
createRoot
public static ByteQuadsCanonicalizer createRoot()
Factory method to call to create a symbol table instance with a randomized seed value.- Returns:
- Root instance to use for constructing new child instances
-
createRoot
protected static ByteQuadsCanonicalizer createRoot(int seed)
-
makeChild
public ByteQuadsCanonicalizer makeChild(int flags)
Factory method used to create actual symbol table instance to use for parsing.- Parameters:
flags- Bit flags of activeJsonFactory.Features enabled.- Returns:
- Actual canonicalizer instance that can be used by a parser
-
makeChildOrPlaceholder
public ByteQuadsCanonicalizer makeChildOrPlaceholder(int flags)
Method similar tomakeChild(int)but one that only creates real instance ofJsonFactory.Feature.CANONICALIZE_FIELD_NAMESis enabled: otherwise a "bogus" instance is created.- Parameters:
flags- Bit flags of activeJsonFactory.Features enabled.- Returns:
- Actual canonicalizer instance that can be used by a parser if (and only if) canonicalization is enabled; otherwise a non-null "placeholder" instance.
- Since:
- 2.13
-
release
public void release()
Method called by the using code to indicate it is done with this instance. This lets instance merge accumulated changes into parent (if need be), safely and efficiently, and without calling code having to know about parent information.
-
mergeChild
private void mergeChild(ByteQuadsCanonicalizer.TableInfo childState)
-
size
public int size()
- Returns:
- Number of symbol entries contained by this canonicalizer instance
-
bucketCount
public int bucketCount()
- Returns:
- number of primary slots table has currently
-
maybeDirty
public boolean maybeDirty()
Method called to check to quickly see if a child symbol table may have gotten additional entries. Used for checking to see if a child table should be merged into shared table.- Returns:
- Whether main hash area has been modified
-
hashSeed
public int hashSeed()
-
isCanonicalizing
public boolean isCanonicalizing()
- Returns:
- True for "real", canonicalizing child tables; false for root table as well as placeholder "child" tables.
- Since:
- 2.13
-
primaryCount
public int primaryCount()
Method mostly needed by unit tests; calculates number of entries that are in the primary slot set. These are "perfect" entries, accessible with a single lookup- Returns:
- Number of entries in the primary hash area
-
secondaryCount
public int secondaryCount()
Method mostly needed by unit tests; calculates number of entries in secondary buckets- Returns:
- Number of entries in the secondary hash area
-
tertiaryCount
public int tertiaryCount()
Method mostly needed by unit tests; calculates number of entries in tertiary buckets- Returns:
- Number of entries in the tertiary hash area
-
spilloverCount
public int spilloverCount()
Method mostly needed by unit tests; calculates number of entries in shared spill-over area- Returns:
- Number of entries in the linear spill-over areay
-
totalCount
public int totalCount()
-
toString
public java.lang.String toString()
- Overrides:
toStringin classjava.lang.Object
-
findName
public java.lang.String findName(int q1)
-
findName
public java.lang.String findName(int q1, int q2)
-
findName
public java.lang.String findName(int q1, int q2, int q3)
-
findName
public java.lang.String findName(int[] q, int qlen)
-
_calcOffset
private final int _calcOffset(int hash)
-
_findSecondary
private java.lang.String _findSecondary(int origOffset, int q1)
-
_findSecondary
private java.lang.String _findSecondary(int origOffset, int q1, int q2)
-
_findSecondary
private java.lang.String _findSecondary(int origOffset, int q1, int q2, int q3)
-
_findSecondary
private java.lang.String _findSecondary(int origOffset, int hash, int[] q, int qlen)
-
_verifyLongName
private boolean _verifyLongName(int[] q, int qlen, int spillOffset)
-
_verifyLongName2
private boolean _verifyLongName2(int[] q, int qlen, int spillOffset)
-
addName
public java.lang.String addName(java.lang.String name, int q1) throws StreamConstraintsException- Parameters:
name- Name to addq1- Quad representation of the name- Returns:
- name (possibly interned)
- Throws:
StreamConstraintsException- if the constraint exceptions
-
addName
public java.lang.String addName(java.lang.String name, int q1, int q2) throws StreamConstraintsException- Parameters:
name- Name to addq1- First quad of name representationq2- Second quad of name representation- Returns:
- name (possibly interned)
- Throws:
StreamConstraintsException- if the constraint exceptions
-
addName
public java.lang.String addName(java.lang.String name, int q1, int q2, int q3) throws StreamConstraintsException- Parameters:
name- Name to addq1- First quad of name representationq2- Second quad of name representationq3- Third quad of name representation- Returns:
- name (possibly interned)
- Throws:
StreamConstraintsException- if the constraint exceptions
-
addName
public java.lang.String addName(java.lang.String name, int[] q, int qlen) throws StreamConstraintsException- Parameters:
name- Name to addq- Quads of name representationqlen- Number of quads inq- Returns:
- name (possibly interned)
- Throws:
StreamConstraintsException- if the constraint exceptions
-
_verifySharing
private void _verifySharing()
-
_findOffsetForAdd
private int _findOffsetForAdd(int hash) throws StreamConstraintsExceptionMethod called to find the location within hash table to add a new symbol in.- Parameters:
hash- Hash of name for which to find location- Throws:
StreamConstraintsException- If name length exceeds maximum allowed.
-
_resizeAndFindOffsetForAdd
private int _resizeAndFindOffsetForAdd(int hash) throws StreamConstraintsException- Throws:
StreamConstraintsException
-
multiplyByFourFifths
static int multiplyByFourFifths(int number)
-
_checkNeedForRehash
private boolean _checkNeedForRehash()
-
_appendLongName
private int _appendLongName(int[] quads, int qlen)
-
calcHash
public int calcHash(int q1)
-
calcHash
public int calcHash(int q1, int q2)
-
calcHash
public int calcHash(int q1, int q2, int q3)
-
calcHash
public int calcHash(int[] q, int qlen)- Parameters:
q- int arrayqlen- length- Returns:
- hash
- Throws:
java.lang.IllegalArgumentException- ifqlenis less than 4
-
rehash
private void rehash() throws StreamConstraintsException- Throws:
StreamConstraintsException
-
nukeSymbols
private void nukeSymbols(boolean fill)
Helper method called to empty all shared symbols, but to leave arrays allocated
-
_spilloverStart
private final int _spilloverStart()
Helper method that calculates start of the spillover area
-
_reportTooManyCollisions
protected void _reportTooManyCollisions() throws StreamConstraintsException- Throws:
StreamConstraintsException
-
_calcTertiaryShift
static int _calcTertiaryShift(int primarySlots)
-
-