Computation and storage of object identity hash values

Techniques for computing and storing object identity hash values are disclosed. In some embodiments, a runtime system generates a value, such as a nonce, that is unique to a particular allocation region within memory. The runtime system may mix the value with one or more seed values that are associated with one or more respective objects stored in the allocation region. The runtime system may obtain object identifiers for the respective objects by applying a hash function to the result of mixing the seed value with at least the value associated with the allocation region. Conditioning operations may also be applied before, during or after the mixing operations to make the values appear more random. The nonce value may be changed from time to time, such as when memory is recycled in the allocation region, to reduce the risk of hash collisions.

TECHNICAL FIELD

The present disclosure relates to efficient computation and storage of object identity hash values in computing systems.

BACKGROUND

Runtime environments for many programming languages manage the allocation of objects within application memory. During or after the allocation process for a new object, the runtime environment may assign a unique object identifier. One approach for assigning an object identifier is to apply a hash function to a seed value obtained by incrementing a global counter. However, the use of incremental seed values may allow users to more easily deduce how the runtime environment generated the unique identifiers, potentially compromising system security and data integrity. Further, if the counter overflows, then repeated seed values will begin to present to the hash algorithm, increasing the likelihood of hash collisions.

DETAILED DESCRIPTION

1. GENERAL OVERVIEW

6. HARDWARE IMPLEMENTATIONS

1. General Overview

Techniques are described herein for optimizing the computation and storage of object identity hash values. In some embodiments, a runtime environment derives object identifiers as a function of seed values a set of one or more other values, also referred to herein as “salt” values. The runtime environment may derive the object identifiers by performing mixing, conditioning, and/or hashing of the seed value, the salt value(s), and/or intermediate values derived based on one or more of the seed value and the salt value(s). The techniques allow the runtime environment to generate unpredictable object identifiers with individual bits that are, or appear to be, statistically independent, thereby improving system security.

The techniques further allow for efficient computation of object identifiers by minimizing the risk of hash collisions. To mitigate the risk of hash collisions, a constraint may be enforced such that the number of distinct hash codes generated exceeds the square of the maximum number of objects alive within the runtime environment at any given moment. The “birthday paradox” dictates that even if a hash code algorithm is perfectly random and may only assume a maximum of 2ndifferent values, then a hash table of more than 2n/2entries is likely to have collisions in excess of the number to be expected if the keys were randomly chosen table indexes. Thus, if hash codes are 32-bits in length, then the performance of hash tables larger than 100,000 entries is likely worse, in terms of computational efficiency, than random assignment. The techniques may further optimize computational efficiency by avoiding the use of cryptographic hash function.

In some embodiments, the runtime environment mixes seed values and/or hash codes with “nonce” values that are unique per allocation region in memory. A nonce may be an arbitrary, random, or pseudo-random value that is assigned once to a corresponding allocation region in memory. The runtime environment may generate unique identifiers for objects stored in the allocation region as a function of the nonce value and one or more other values, including a seed value, for the object. For example, the runtime environment may mix bits of the nonce value with the seed value and apply a hash function to the combined value to derive a hash value. The resulting hash value may be used as the object identifier or further conditioned to derive the object identifier. As another example, the runtime environment may apply a hash function to a conditioned or unconditioned seed value to derive a hash value. The runtime environment may then condition the hash value and/or mixing the hash value with bits of a nonce value to derive the object identifier.

In some embodiments, memory addresses are used as seed values to derive object identifiers. A memory address uniquely identifies an object at a given point in time. However, at different points in time, several objects may be allocated at the same location in memory, leading to a paucity of distinct seed value, and hence hash collisions in tables larger than the square of distinct seed values. Adding a nonce and/or other salt values may ensure that hash codes of objects successively allocated at the same address differ, as long as different salt values are applied to the successively allocated objects. The runtime environment may ensure different salt values are applied to successively allocated objects by changing the nonce assigned to an allocation region where the objects are stored at least as frequently as memory reclamation events occur within the allocation region. In runtime environments with garbage collection, for example, a new nonce may be assigned to an allocation region each time garbage collection is run within the allocation region.

In some embodiments, other sources of salt may be combined with seed values and/or hash codes. Sources of salt may be extracted from the object itself, such as from an immutable field. Additionally or alternatively, sources external to the object may be used to provide salt values. The sources of salt may be used singly or in combination to condition seed values and/or hash codes.

Embodiments described herein allow hash codes and object identifiers of any size including greater than the machine word size of the system generating the object identifiers. A constraint may be imposed such that the number of objects in recycled areas of memory times the number of salt values is larger than the square of the total number of objects which may be presented to a single hash table. The object identifier size may be predefined, selected by a user, automatically scaled based on the number of objects created within the runtime environment, or determined based on other criteria.

In addition or as an alternative to object identity hashes, embodiments described herein allow for structural hashes of data objects. A structural hash may be mapped to a particular object value, which may not be unique to a single data object at a given point in time. For example, a structural hash may be generated as a function of a string value such that multiple data objects with the same string value are mapped to the same structural hash. In some embodiments, structural hashes are generated as a function of a value extracted from the data object and one or more salt values. The salt values may include a session-based nonce value that is arbitrarily or randomly generated each time a new session with the runtime environment is initiated. Session-based nonce values may be used such that identical object values, which may span multiple allocation regions, map to the same hash code during a given runtime session.

In some embodiments, the techniques described herein for generating and managing object identifiers and hash values are executed within a runtime environment. A runtime environment in this context may include supporting code, tools and/or other hardware/software components that implement a program's execution. One or more components of the runtime environment may vary depending on the programming language of the program's source code, the hardware platform on which the program is executed, the operating system version, and/or other system attributes.

FIG.1illustrates an example computing architecture in which techniques described herein may be practiced. Software and/or hardware components described with relation to the example architecture may be omitted or associated with a different set of functionality than described herein. Software and/or hardware components, not described herein, may be used within an environment in accordance with some embodiments. Accordingly, the example environment should not be constructed as limiting the scope of any of the claims.

As illustrated inFIG.1, computing architecture100includes source code files102which are compiled by compiler104into blueprints representing the program to be executed. Examples of the blueprints include class files106, which may be loaded and executed by execution platform108. Execution platform108includes runtime environment126, operating system124, and one or more application programming interfaces (APIs)122that enable communication between runtime environment126and operating system124. Runtime environment126includes virtual machine110comprising various components, such as memory manager112(which may include a garbage collector), class file verifier114to check the validity of class files106, class loader116to locate and build in-memory representations of classes, interpreter118for executing virtual machine code, and just-in-time (JIT) compiler120for producing optimized machine-level code.

In some embodiments, computing architecture100includes source code files102that contain code written in a particular programming language, such as Java, C, C++, C#, Ruby, Perl, and so forth. Thus, source code files102adhere to a particular set of syntactic and/or semantic rules for the associated language. For example, code written in Java adheres to the Java Language Specification. However, since specifications are updated and revised over time, source code files102may be associated with a version number indicating the revision of the specification to which source code files102adhere. One or more of source code files102may be written in a programming language supported by automatic garbage collection.

In various embodiments, compiler104converts the source code, which is written according to a specification directed to the convenience of the programmer, to either machine or object code, which is executable directly by the particular machine environment, or an intermediate representation (“virtual machine code/instructions”), such as bytecode, which is executable by virtual machine110that is capable of running on top of a variety of particular machine environments. The virtual machine instructions are executable by virtual machine110in a more direct and efficient manner than the source code. Converting source code to virtual machine instructions includes mapping source code functionality from the language to virtual machine functionality that utilizes underlying resources, such as data structures. Often, functionality that is presented in simple terms via source code by the programmer is converted into more complex steps that map more directly to the instruction set supported by the underlying hardware on which the virtual machine110resides.

In some embodiments, the virtual machine110includes an interpreter118and a JIT compiler120(or a component implementing aspects of both), and executes programs using a combination of interpreted and compiled techniques. For example, the virtual machine110may initially begin by interpreting the virtual machine instructions representing the program via the interpreter118while tracking statistics related to program behavior, such as how often different sections or blocks of code are executed by the virtual machine110. Once a block of code surpass a threshold (is “hot”), the virtual machine110may invoke the JIT compiler120to perform an analysis of the block and generate optimized machine-level instructions which replaces the “hot” block of code for future executions. Since programs tend to spend most time executing a small portion of overall code, compiling just the “hot” portions of the program can provide similar performance to fully compiled code, but without the start-up penalty. Furthermore, although the optimization analysis is constrained to the “hot” block being replaced, there still exists far greater optimization potential than converting each instruction individually. There are a number of variations on the above described example, such as tiered compiling.

In other embodiments, the runtime environment126may not include a virtual machine. For example, some static and stack-based environments do not execute programs using a virtual machine. A runtime environment may include supporting code, tools and/or other hardware/software components that implement a given program's execution. One or more components of the runtime environment may vary depending on the programming language of the source code, the hardware platform on which the program is executed, and/or the operating system version.

The source code files102have been illustrated as the “top level” representation of the program to be executed by the execution platform108. Although the computing architecture100depicts the source code files102as a “top level” program representation, in other embodiments the source code files102may be an intermediate representation received via a “higher level” compiler that processed code files in a different language into the language of the source code files102.

In some embodiments, the compiler104receives as input the source code files102and converts the source code files102into class files106that are in a format expected by the virtual machine110. For example, in the context of the JVM, the Java Virtual Machine Specification defines a particular class file format to which the class files106are expected to adhere. In some embodiments, the class files106contain the virtual machine instructions that have been converted from the source code files102. However, in other embodiments, the class files106may contain other structures as well, such as tables identifying constant values and/or metadata related to various structures (classes, fields, methods, and so forth).

FIG.2illustrates example virtual machine memory layout200according to some embodiments. A virtual machine (e.g., virtual machine110) may adhere to the virtual machine memory layout200depicted inFIG.2. In other embodiments, the memory layout of the virtual machine110may vary, such as by including additional components and/or omitting one or more of the depicted components, depending on the runtime environment. Although components of the virtual machine memory layout200may be referred to as memory areas or allocation regions, there is no requirement that the areas and regions are physically contiguous.

In the example illustrated byFIG.2, the virtual machine memory layout200is divided into a shared area202and a local thread area218. The shared area202represents an area in memory storing structures and objects that are shared among the various threads executing on the virtual machine110. The shared area202includes a heap204and aper-class area210. The local thread area218represents an area that stores structures and objects that are local to threads and not shared with other threads. The local thread area218may include or correspond to one or more thread local allocation buffers, also referred to as TLABs.

The heap204represents an area of memory allocated on behalf of a program during execution of the program. In some embodiments, the heap204includes a young generation206and a tenured generation208. The young generation206may correspond to regions of the heap that stores newly created objects during program execution. When the young generation206is filled, the oldest objects are promoted to the tenured generation208to free up space for new objects in the young generation206. Promoting an object may comprise moving the object to a different region and/or reclassifying the object.

A per-class area210represents the memory area where the data pertaining to the individual classes are stored. In some embodiments, the per-class area210includes, for each loaded class, a run-time constant pool212representing data from a constant table of the class, field and method data214(for example, to hold the static fields of the class), and method code216representing the virtual machine instructions for methods of the class.

As previously mentioned, the local thread area218represents a memory area where structures specific to individual threads are stored. InFIG.2, the local thread area218includes thread structures220and thread structures226, representing the per-thread structures utilized by different threads. In order to provide clear examples, the local thread area218depicted inFIG.2assumes two threads are executing on the virtual machine110. However, in a practical environment, the virtual machine110may execute any arbitrary number of threads, with the number of thread structures scaled accordingly.

In some embodiments, the thread structures220include the program counter222and the thread stack224. Similarly, the thread structures226include the program counter228and the thread stack230.

In some embodiments, the program counter222and the program counter228store the current address of the virtual machine instruction being executed by their respective threads. Thus, as a thread steps through the instructions, the program counters are updated to maintain an index to the current instruction.

In some embodiments, the thread stack224and the thread stack230each store stack frames for their respective threads, where each stack frame holds local variables for a function. A frame is a data structure that may be used to store data and partial results, return values for methods, and/or perform dynamic linking. A new frame is created each time a method is invoked. A frame is destroyed when the method that caused the frame to be generated completes. Thus, when a thread performs a method invocation, the virtual machine110generates a new frame and pushes the frame onto the virtual machine stack associated with the thread.

When a method invocation completes, the virtual machine110passes back the result of the method invocation to the previous frame and pops the current frame off of the stack. In some embodiments, for a given thread, one frame is active at any point. This active frame is referred to as the current frame, the method that caused generation of the current frame is referred to as the current method, and the class to which the current method belongs is referred to as the current class.

The thread stack224and the thread stack230may correspond to native operating system stacks or virtual thread stacks. Generally, the number of virtual threads executing on a machine is much greater than the number of native threads.

FIG.3illustrates an example frame layout for a frame300according to some embodiments. In some embodiments, frames of a thread stack, such as the thread stack224and the thread stack230adhere to the structure of the frame300.

In some embodiments, the frame300includes local variables302, an operand stack304, and a run-time constant pool reference table306. In some embodiments, the local variables302are represented as an array of variables that each hold a value, for example, boolean, byte, char, short, int, float, or reference. Further, some value types, such as longs or doubles, may be represented by more than one entry in the array. The local variables302may be used to pass parameters on method invocations and store partial results. For example, when generating the frame300in response to invoking a method, the parameters may be stored in predefined positions within the local variables302, such as indexes 1-n corresponding to the first to nthparameters in the invocation. The parameters may include pointers and other references.

In some embodiments, the operand stack304is empty by default when the frame300is created by the virtual machine110. The virtual machine110then supplies instructions from the method code216of the current method to load constants or values from the local variables302onto the operand stack304. Other instructions take operands from the operand stack304, operate on them, and push the result back onto the operand stack304. Furthermore, the operand stack304is used to prepare parameters to be passed to methods and to receive method results. For example, the parameters of the method being invoked could be pushed onto the operand stack304prior to issuing the invocation to the method. The virtual machine110then generates a new frame for the method invocation where the operands on the operand stack304of the previous frame are popped and loaded into the local variables302of the new frame. When the invoked method terminates, the new frame is popped from the virtual machine stack and the return value is pushed onto the operand stack304of the previous frame.

In some embodiments, the run-time constant pool reference table306contains a reference to the run-time constant pool of the current class (e.g., the runtime constant pool212). The run-time constant pool reference table306is used to support resolution. Resolution is the process whereby symbolic references in the constant pool are translated into concrete memory addresses, loading classes to resolve as-yet-undefined symbols and translating variable accesses into appropriate offsets into storage structures associated with the run-time location of these variables.

3. Object Identifier Computation

3.1 Process Overview

In some embodiments, object identifiers are computed for objects allocated within a runtime environment, such as the runtime environment126. Example objects may include variables, data structures, functions, class objects, methods, and primitive datatypes. An object may correspond to one or more storage regions where an object value or set of values are stored. The value or set of values may be accessed using the unique identifier assigned to the object. An object may be stored in a region accessible to multiple threads or a region that is local to single thread, such as a TLAB.

FIG.4illustrates an example set of operations for generating conditioned object identifiers according to some embodiments. One or more operations illustrated inFIG.4may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.4should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.4, the process obtains a seed value for an object (operation402). The seed value that is used may vary depending on the particular implementation. In some embodiments, the seed value is one that is temporally or otherwise related to the object at the time the process is executing. For example, the seed value may be a memory address identifying a location in memory where the object is currently stored. As another example, the process may obtain a seed value by obtaining a current value from a global counter. Other sources may also be used to obtain a seed value.

In some embodiments, the process determines whether to condition and/or add salt values the seed value (operation404). If so, then the process proceeds by conditioning the seed value and/or mixing the salt values (operation406). The salt may be added before, during, or after conditioning of the seed value. In other cases, the salt may be added to an unconditioned seed value or the seed may be conditioned without adding salt. The manner in which the seed value is conditioned may vary from implementation to implementation. As an example, a 32-bit seed may be multiplied by a 64-bit pseudo-random constant and a bitfield extracted from the middle of the 128-bit result. As another example, the seed value may be subjected to a cascade of shift and XOR operations. Additionally or alternatively, other conditioning functions may be applied. The conditioning functions may “stretch” and “mix” the seed value into a bit-vector of a desired size whose bits appear random.

In some embodiments, if the salt is not already random, then the salt may be conditioned in addition or as an alternative to the seed value. For example, one or more of the aforementioned conditioning functions, such as the cascade of shift and XOR operations, may be applied to a salt value. The pre-conditioned salt may then be mixed with a conditioned or unconditioned seed value. A mixing function may receive, as input, the salt value(s) and seed value. The mixing function may mix the bits of the input values according to predefined logic and output the resulting bit-vector.

The process further applies a hash function to derive a hash code (operation408). In some embodiments, the hash function is applied to the value obtained by conditioning and/or mixing operations described above. In other embodiments, the hash function may be applied to an unconditioned seed without any added salt. A hash function may take the value, which may be arbitrary in size, as input, and map the value to a fixed-size hash code. In some embodiments, a non-cryptographic hash function is used to reduce processing overhead within the runtime environment. Example non-cryptographic hash functions include the MD5 message-digest algorithm and rolling hash functions. Other cryptographic and/or non-cryptographic hash functions may be used, depending on the particular implementation.

In some embodiments, the process determines whether to condition and/or add salt values the hash code (operation410). If so, then the process proceeds by conditioning the hash code and/or adding the salt values (operation412). One or more techniques described in connection with operation406for conditioning the seed value and/or mixing salt may be applied to the hash code.

The process further returns the conditioned or unconditioned hash code as the unique identifier for the object (operation414). The object identifier may be provided to other applications and/or users as a handle to access the corresponding object. Applications may include the object identifier in requests to read one or more values from the referenced object. The runtime environment126may use the object identifier provided in the request to locate the corresponding object in memory and return the requested value(s).

In some embodiments, the runtime environment126assigns unique nonce values to allocation regions in memory. A nonce may be assigned as an arbitrary, random, or pseudo-random value, such as a global number. The nonce may be unique and used only once per runtime session for a given allocation region. The runtime environment126may use the nonce value assigned to an allocation region as a source of salt for objects that are allocated within the region. The same nonce value may be shared as salt for multiple objects that are stored in the same allocation region. Thus, a nonce value may be used more than once to generate multiple distinct object identifiers, which mitigates the processing overhead of generating random or pseudo-random salt for each newly allocated object.

In some embodiments, allocation regions include one or more shared memory regions, such as the shared area202. Nonce values may be computed for each shared memory region, where each shared memory region may comprise one or more memory segments. The runtime environment126may compute object identifiers for objects that are allocated within the shared area202as a function of the nonce assigned to the shared area202and a seed value associated with the object. The bits of the nonce may be mixed with the seed value and/or hash code as previously described to obtain the object identifier. Other sources of salt may also be mixed in, depending on the particular implementation.

Additionally or alternatively, an allocation region and corresponding nonce value may be localized. For example, a nonce may be computed as part of a thread local allocation buffer provisioned by a virtual machine for use by a given thread. Objects allocated within a given instance of the thread local allocation buffer may also be associated with the nonce assigned to the buffer, and the nonce may be used as salt to compute corresponding object identifiers.

Additionally or alternatively, a nonce value may be assigned per segment of memory, such as a virtual memory page. Objects allocated within a given virtual memory page may be associated with the nonce assigned to the memory segment, and the nonce may be used as salt to compute corresponding object identifiers for the objects allocated within the virtual memory page.

FIG.5illustrates an example dataflow for computing object identifiers as a function of allocation-based nonce values and memory address according to some embodiments. Allocation region500and allocation region508represent different areas within memory from which the runtime environment126may allocate new objects. Nonce502is associated with objects allocated within allocation region500, including objects allocated at object address504and object address506. Nonce510is associated with objects allocated within allocation region508, including objects allocated at object address512. It is noted that the number of allocation regions, nonce values, and objects per allocation region may vary from that depicted inFIG.5depending on the runtime environment and/or the current state of program execution.

An object ID service516comprises one or more threads for computing object identifiers522. The object ID service516includes a mixing function518and a hash function520. The mixing function518receives, as input, two or more input values and outputs a bit-vector computed by mixing the bits of the two or more input values according to predefined mixing logic. Mixing may include shifting, extending, padding, and/or applying logical operators, such as the XOR and AND operators, to the input bit-vectors. In some embodiments, the input bit-vectors include an object address and a nonce associated with an object. The object address may be referred to as the seed value and the nonce as the salt to be mixed with the seed. As an example, the mixing function518may mix all or a subset of the bits of the object address504with the nonce502to obtain an intermediate value for the object located by object address504. Similarly, the mixing function518may mix the bits of the object address506with the nonce502and the object address512with the nonce510to compute respective intermediate values for the corresponding objects.

In some embodiments, the mixing function518mixes one or more other salt value(s)514in addition or as an alternative to the nonce. Example sources of other salt values are described in further detail in Section 3.3, titled “Sources of Salt”, below.

Additionally or alternatively, the mixing function518may perform conditioning operations to stretch and mix seed values (e.g., object address504, object address506, object address512), salt values (e.g., nonce502, nonce510, other salt value(s)514), intermediate values, and/or hash codes. For example, a seed, salt, intermediate value, and/or hash code may be multiplied by a random constant or subjected to a cascade of shift and XOR operations as previously described.

The hash function520is configured to take a value, such as the intermediate value output by the mixing function518, and output a hash code. The resultant hash code may be used as the object identifier. In other embodiments, the hash code may be fed back through the mixing function518for conditioning and/or mixing with additional salt values to generate the final object identifier.

In some embodiments, the mixing function518may mix salt with other sources of seed values. For example, the object ID service516may maintain a global counter. When a request to generate an object identifier is received, the object ID service516may use the current value as the seed and increment the counter or, alternatively, increment the counter and use the incremented value as the seed. The count value may then be mixed with a nonce and/or other salt value(s)514.

3.3 Sources of Salt

As previously mentioned, other sources of salt may be mixed or otherwise added to a seed value in addition or as an alternative to the allocation-based nonce value. In some embodiments, the other sources of salt include intrinsic salt values. Intrinsic salt refers to values that are extracted from the object itself. If an object has an immutable field, which it retains throughout its lifetime, then salt may be obtained from the value of that field. Multiple fields may provide multiple independent sources of intrinsic salt. For example, the “class” field of objects in some programming languages is an immutable field that stores a class identifier, such as a class identity hash code. As another example, a final field may be used if the runtime environment126successfully verifies that the field will never be changed. In these examples, since the salt is an intrinsic property of the object, it may alternatively be viewed as additional “seed” bits. The difference between seed and salt is, thus, unimportant as they are mixed together. As such, the use of these two terms is an expository aid rather than a mathematical distinction.

In some embodiments, the source of salt may include extrinsic salt, which originates from outside the object. Extrinsic salt may be used with many objects if their seeds differ or the combination with other salt values is unique. Shared salt may leverage more computationally demanding sources with negligible performance impact since the cost of creation is amortized over multiple objects. Examples include hardware “random number” queries to obtain a value from a hardware random number generator, timer queries to obtain timestamp values, and cryptographic hashes. Additionally or alternatively, other sources of extrinsic salt, such as a pseudo-random number generator (PRNG), may be used. If not already random, the salt may be pre-conditioned by a mixing function such that the bits appear random.

One or more sources of extrinsic salt may be used as a nonce value. The nonce value may include allocation-based nonce values that are assigned to particular allocation region as previously described. Additionally or alternatively, nonce values may be associated with groups of objects through other attributes. For example, the runtime environment126may generate a new nonce value each time a new session is initiated. If an allocation-based nonce value is not available, then the session-based nonce value may be used as salt.

4.1 Updating and Storing Values

Nonce and other salt values may be changed from time to time. Updating the nonce values may prevent duplicate combinations of seed and salt values from being fed to the hash function520. If an object address is used as a seed value, then the risk of a collision arises in the event memory is recycled and a different object is stored at the same address. If a global counter is used as a seed value, then the risk of a collision arises in the event that the counter overflows. Responsive to such events, the allocation-based nonce and/or other salt values may be changed to avoid collisions.

In some embodiments, events may further trigger storage of information sufficient to recompute or otherwise redetermine an object identifier. For example, the result of generating an identifier for an object may be recorded by permanently associating, with the object, any part of the seed or salt that cannot be recomputed from the object. For counter-based seeds, the counter may be immediately stored with the object. For pointer-based seeds, the storage may be delayed until the object is moved to a new location, such as by a garbage collector. For field-based (intrinsic salt), no additional recording is needed since the value may be extracted from the object itself. For extrinsic salt such as nonce values, recording may be performed before the salt changes. In the case of nonce values associated with a local buffer or memory segment, for instance, the nonce may be recorded along with the original seed value before the nonce for the allocation region is changed.

In some embodiments, the recording techniques may be applied to an intermediate value obtained by combining and/or conditioning the seed and salt values. For example, an intermediate value may be obtained by mixing an object address with an allocation-based nonce value and then conditioning the combined values. The resulting intermediate value may be recorded in addition or as an alternative to the seed and salt values. The object identifier may be obtained by applying a hash function to the intermediate value to derive a hash code. Additionally or alternatively, a fully conditioned identity hash code may be recorded responsive to any of the aforementioned events.

FIG.6illustrates an example set of operations for storing and refreshing nonce values responsive to memory reclamation events according to some embodiments. One or more operations illustrated inFIG.6may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.6should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.6, the process assigns unique nonce values per allocation region (operation602). For example, when a slab of memory is readied for allocation, such as a thread local allocation buffer in the young generation, the process may compute a random or pseudo-random nonce value having a particular width (e.g., 64 bit, 128 bit, etc.). The unique nonce may be used as shared salt across objects stored within the allocation region as previously described.

The process further detects a memory reclamation event in one or more of the allocation regions (operation604). A memory reclamation event may involve moving an object from one allocation region to another. In runtime environments with generational garbage collection, for example, objects may be moved from the young generation to the tenured generation. In other cases, objects may be moved to other regions, depending on the particular runtime environment, to reclaim space and/or optimize the memory layout.

Responsive to detecting the memory reclamation event, the process records the object identifiers and/or other values sufficient to recompute the object identifiers for live objects in the allocation region (operation606). For example, the process may store an allocation-based nonce, an object address, and/or an intermediate value associated with an object being moved from the allocation region. As another example, the process may compute and store a fully conditioned hash code associated with the object.

In some embodiments, the recorded information is stored in the object header if there is sufficient space. In other embodiments, when a garbage collector or other memory reclamation process moves an object to a new address, then the process may allocate a side record adjacent to the object in the new location and store the recorded information in the record. In other embodiments, the information may be stored in a table indexed by some property of the object, such as the new location and/or value stored in the object headers. The process may mark the object as having stored the recorded information. The runtime environment126may determine whether an object has had its identifier computed and recorded based on whether the object has been marked.

Once the information has been recorded, the process assigns a new nonce value to each allocation region that was subject to the memory reclamation event (operation608). The new nonce value may be a pseudo-random or random number that has not been previously used for the allocation region during the runtime session. The new nonce value may be used to compute object identifiers for objects in the allocation region that have not previously had their object identifiers computed. The previous nonce value may no longer be used for newly allocated objects so that different objects consecutively stored at the same memory address have different added salt resulting in different object identifiers. If an object has had their object identifier computed prior to the nonce update, then the runtime environment126may use the recorded information, which may include the previous nonce value. The recorded information may be persisted throughout the life of the runtime session.

In some embodiments, the runtime environment126may support multiple available widths of identity hash codes. For example, the runtime environment126may support 32-bit, 80-bit, and 256-bit hash codes. Additionally or alternatively, other widths of hash codes may be supported, depending on the particular implementation. The runtime environment126may further support different qualities of identity hash codes, such as cryptographic and non-cryptographic hash codes. The width and/or quality of the hash code may be predetermined or selected by a user when a runtime session is initiated. In other cases, the width and/or quality of hash code may be configurable during the runtime session.

In some embodiments, a request for an object identifier may specify the length and/or quality of an object identifier. For example, an application may request a cryptographic or non-cryptographic identity hash having a particular width in bits. In response, the virtual machine110may compute only the bits that have been requested and save seed and salt values to reproduce them reliably on request. If a new request for a larger or higher-quality hash code is made later, new salt may be added and/or more conditioning may be applied, such as by running SHA-256 with secret salt. If the additional salt is used, then it may also be recorded for the object in addition to the salt that was previously used to compute the smaller or lower-quality hash code.

In some embodiments, the length and/or quality of an object identifier may be automatically selected based on one or more runtime parameters. For example, the virtual machine110may select a bit-width for an identity hash code based on how many objects have been created during a runtime session. When the runtime session is first initiated, the width may be relatively small (e.g., the machine word size or smaller) without risking performance degradation from hash collisions. As the number of objects increases, the width may be increased to ensure that the number of distinct hash codes generated exceeds the square of the maximum number of objects alive within the runtime environment at any given moment.

FIG.7illustrates an example set of operations for dynamically adjusting the length of object identifiers according to some embodiments. One or more operations illustrated inFIG.7may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.7should not be construed as limiting the scope of one or more embodiments.

The process includes initializing a length for the object identifiers (operation702). For example, when a new runtime session is initiated, then the process may default to the lowest available bit-width for an identity hash code. As previously indicated, the lowest bit-width may be the machine word size or smaller. However, the initial width may vary depending on the particular implementation.

The process further includes detecting a new object allocation (operation704). The process may increment a counter to track how many objects have been allocated during a runtime session. In some cases, the counter may track the total number of objects created over the lifetime of the runtime session. In other embodiments, the counter may track only the total number of live objects. In the latter case, the counter may be decremented when an object is deleted.

The process may determine, based on the counter, whether the number of objects exceeds a threshold (operation706). The threshold may be selected such that the square of the maximum number of objects alive within the runtime environment is not less than the number of distinct hash codes that may be computed for a selected bit-width.

If the threshold is exceeded, then, the length of the object identifiers is increased (operation708). Multiple thresholds may be used to gradually step up the length as the number of live objects grows. For example, the length may be initially increased from 32-bit to 80-bit if a first threshold is exceeded. If a second threshold is exceeded, then the length may be increased form 80-bit to 256-bit or some other length. The thresholds and lengths may vary from implementation to implementation.

The process further generates an object identifier having the currently selected length (operation710). This may be done when the object is first allocated or subsequently responsive to a request for an object identifier.

The process determines whether to continue monitoring new allocations for a runtime session (operation712). The virtual machine110may continue monitoring during the life of a runtime session, and the process may return to operation704for each new object allocation.

In some embodiments, the techniques described herein may be applied to structural hashes. Structural hashes differ from identity hashes in that two distinct objects are mapped to the same hash code if the objects share the same value. Objects with identical values may be stored in distinct allocation regions within the runtime environment126. In these instances, the same nonce value, such as a session-based nonce, may be used across different allocation regions. The nonce value may be maintained throughout the life or a runtime session to ensure that structural hashes of the same object value are mapped to the same hash code for a given runtime session.

FIG.8illustrates an example dataflow for computing structural hashes as a function of session-based nonce values and object values according to some embodiments. Runtime session800includes nonce802, object804, object806, and object808. The nonce802may be generated when the runtime session800is initiated and persisted without changing through the life of runtime session800.

A structural hash generator810comprises one or more threads for computing structural hash code(s)818. The structural hash generator810includes a mixing function812and a hash function814. The mixing function812receives, as input, two or more input values and outputs a bit-vector computed by mixing the bits of the two or more input values according to predefined mixing logic. Mixing may include shifting, extending, padding, and/or applying logical operators to the input bit-vectors. In some embodiments, the input bit-vectors include a value extracted from the object and a nonce. As an example, the mixing function812may the bits from object804, object806, and/or object806with the nonce802. The mixing function812may mix one or more other salt value(s)816in addition or as an alternative to the nonce802. The mixing function518may further perform conditioning operations to stretch and mix the object values, salt values, intermediate values, and/or hash codes as previously described.

The hash function814is configured to take a value, such as the intermediate value output by the mixing function812, and output a hash code. The resultant hash code may be used as a structural hash for an object. In other embodiments, the hash code may be fed back through the mixing function812for conditioning and/or mixing with additional salt values to generate the final structural hash. The structural hash generator810may generate the same structural hash for object804, object806, and/or object808if the object values are identical. For example, if two or more of the objects may be strings storing the same sequence of characters. The structural hash generator810may mix the same salt and perform the same conditioning for each object resulting in identical structural hash codes for different objects that store the same string value.

6. Hardware Overview

For example,FIG.9is a block diagram that illustrates a computer system900upon which an embodiment of the invention may be implemented. The computer system900includes a bus902or other communication mechanism for communicating information, and a hardware processor904coupled with the bus902for processing information. A hardware processor904may be, for example, a general-purpose microprocessor.

The computer system900further includes a read only memory (ROM)908or other static storage device coupled to the bus902for storing static information and instructions for the processor904. A storage device910, such as a magnetic disk or optical disk, is provided and coupled to the bus902for storing information and instructions.

The computer system900may be coupled via the bus902to a display912, such as a cathode ray tube (CRT) or light emitting diode (LED) monitor, for displaying information to a computer user. An input device914, which may include alphanumeric and other keys, is coupled to bus902for communicating information and command selections to processor904. Another type of user input device is a cursor control916, such as a mouse, a trackball, touchscreen, or cursor direction keys for communicating direction information and command selections to the processor904and for controlling cursor movement on the display912. The input device914typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

The computer system900may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system900to be a special-purpose machine. According to one embodiment, the techniques herein are performed by the computer system900in response to the processor904executing one or more sequences of one or more instructions contained in the main memory906. Such instructions may be read into the main memory906from another storage medium, such as the storage device910. Execution of the sequences of instructions contained in the main memory906causes the processor904to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to the processor904for execution. For example, the instructions may initially be carried on a magnetic disk or solid-state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a network line, such as a telephone line, a fiber optic cable, or a coaxial cable, using a modem. A modem local to the computer system900can receive the data on the network line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on the bus902. The bus902carries the data to the main memory906, from which the processor904retrieves and executes the instructions. The instructions received by the main memory906may optionally be stored on the storage device910either before or after execution by the processor904.

The computer system900also includes a communication interface918coupled to the bus902. The communication interface918provides a two-way data communication coupling to a network link920that is connected to a local network922. For example, the communication interface918may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, the communication interface918may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, the communication interface918sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

A network link920typically provides data communication through one or more networks to other data devices. For example, the network link920may provide a connection through a local network922to a host computer924or to data equipment operated by an Internet Service Provider (ISP)926. ISP926in turn provides data communication services through the worldwide packet data communication network now commonly referred to as the “Internet”928. The local network922and the Internet928both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on the network link920and through the communication interface918, which carry the digital data to and from the computer system900, are example forms of transmission media.

The computer system900can send messages and receive data, including program code, through the network(s), the network link920and the communication interface918. In the Internet example, a server930might transmit a requested code for an application program through the Internet928, the ISP926, the local network922and the communication interface918.

The received code may be executed by the processor904as it is received, and/or stored in the storage device910, or other non-volatile storage for later execution.