KR20170122091A - Chunk allocation method for performing memory controller of storage device and memory controler - Google Patents

Abstract

The present invention relates to a chunk allocation method and a memory controller performed by a memory controller of a storage device.
In other words, upon receiving a request to allocate a new chunk from the host device to the heap area, the chunk allocation method determines whether or not allocation is possible to a segment of memory, and if not, To allocate a chunk to an empty space of the formed memory or ii) to allocate a chunk to a new memory depending on whether a free space of the memory is formed.

Description

CHUNK ALLOCATION METHOD FOR PERFORMING MEMORY CONTROLLER OF STORAGE DEVICE AND MEMORY CONTROLLER,

The following description relates to a chunk allocation method and a memory controller performed by a memory controller of a storage device. When a request to allocate a chunk from a host device is received, the memory controller of the storage device stores the chunk allocation A chunk allocation method and a memory controller of a storage device that allocate a chunk to an empty segment of a segment of memory when allocation is possible.

In general, objects in non-volatile memory (NVM) can be permanently preserved without power. In other words, objects stored in nonvolatile memory can be permanently stored in memory, unless the user explicitly deletes them, and if such garbage is continuously loaded into nonvolatile memory, it will cause a fatal space overhead in the system Therefore, a garbage collection technique for solving this is essential for a storage device using a nonvolatile memory.

In the garbage collection, as described above, the objects stored in the nonvolatile memory are permanently preserved unless the user explicitly deletes them. Therefore, most of the garbage collection techniques that have been developed have a problem in that the user can access the data The garbage is judged to be in the nonvolatile memory.

However, techniques for allocating memory based on nonvolatile memory are difficult to manage the number of references of objects, and it is difficult to perform basic garbage collection. Specifically, an object stored in the nonvolatile memory is garbage-occupied depending on the presence of metadata (pointers) that can access each object stored in the nonvolatile memory, thereby permanently occupying the space of the nonvolatile memory. Thus, if there is no metadata to access an object stored in the non-volatile memory, access to it is impossible.

Therefore, in order to find out the garbage in the non-volatile memory, it is necessary to determine whether the object stored in the nonvolatile memory is configured in order to determine whether or not the object is referred to at the system level, And so on.

In addition, when the processor is currently in use, the garbage collection for the non-volatile memory matched to the processor can not be performed. Therefore, the processor such as the server or the daemon can not perform the garbage collection forever, I can not help but notice.

Therefore, there is a need for a method capable of identifying the type information of the object stored in the nonvolatile memory and the pointer position, and performing garbage collection irrespective of the current operation of the processor.

The present invention can provide a chunk allocation method capable of dividing the heap area of the host device into 'object storage' units and performing the garbage collection unit for the segmented object storage.

The present invention can provide a chunk allocation method capable of performing garbage collection on a segment of memory without stopping a processor executing in the host apparatus in allocating a chunk to the storage apparatus.

A method of allocating a chunk performed by a memory controller of a storage device includes receiving a request from a host device to allocate a chunk to a segment of memory corresponding to an object store of the heap area; Determining whether the chunk is allocatable to a segment of memory in response to the received request; Performing garbage collection on a segment of memory using an allocation list if the chunk is not allocatable to a segment of the memory; Determining whether the chunk is allocable to a segment of memory in which garbage collection has been performed; And allocating the chunk to a segment of memory according to a determination result.

The step of determining whether allocating to a segment of memory according to an embodiment may determine whether the chunk is allocated to an empty segment of a segment of memory corresponding to the object store.

The step of performing garbage collection according to an exemplary embodiment may perform garbage collection considering whether a physical address indicating pages constituting a segment of the memory is searched in the allocation list.

The step of performing garbage collection according to an exemplary embodiment may include determining a page of a segment having the physical address not to be retrieved as garbage when the physical address is not retrieved from the allocation list, Can perform garbage collection on a segment of memory.

The object storage according to an exemplary embodiment is divided into a metadata area in which a type of a data structure for allocating a chunk to a segment of the memory is stored and a user data area in which data is stored, Lt; / RTI >

The allocation list according to an embodiment includes physical addresses of the nodes searched for in the user data area based on the data structure stored in the metadata area, .

The step of determining whether allocation of a segment of a memory in which garbage collection has been performed according to an exemplary embodiment may include: i) a segment of a memory that has been emptied in the process of performing the garbage collection; or ii) It is possible to determine whether allocations are possible in consideration of at least one of the segments of the memory that have not been emptied of the segments of the memory but are already emptied of the segments of the memory.

The allocating of the chunks according to an exemplary embodiment may allocate the chunks to the segment of the empty memory if it is possible to allocate the segment to the memory in which the garbage collection has been performed.

The step of allocating the chunks according to an embodiment may include allocating the chunks to segments of different memory rather than segments of the memory corresponding to the object store if the allocation of the chunks to segments of the memory in which garbage collection has been performed is impossible can do.

The memory controller performing the chunk allocation method according to an embodiment receives a request for allocating a chunk from a host device to a segment of a memory corresponding to an object store of the heap area, If the chunk can not be allocated to a segment of the memory, it is determined whether or not the chunk is allocated to a segment of the memory. In this case, the chunk is subjected to garbage collection on a segment of the memory using the allocation list, It is possible to determine whether or not the segment can be allocated, and allocate the chunk to the segment of the memory according to the determination result.

The memory controller according to an exemplary embodiment may determine whether the chunk is allocated to an empty segment of a segment of memory corresponding to the object store.

The memory controller according to an exemplary embodiment may perform garbage collection in consideration of whether a physical address indicating pages constituting a segment of the memory is retrieved from the allocation list.

The memory controller according to an embodiment determines a page of a segment having the non-retrievable physical address as garbage when the physical address is not retrieved from the allocation list, Can be performed.

The object storage according to an exemplary embodiment is divided into a metadata area in which a type of a data structure for allocating a chunk to a segment of the memory is stored and a user data area in which data is stored, Lt; / RTI >

The allocation list according to an embodiment includes physical addresses of the nodes searched for in the user data area based on the data structure stored in the metadata area, .

The step of determining whether allocation of a segment of the memory in which the garbage collection has been performed according to an embodiment may include the steps of i) a segment of the memory that has been emptied in the course of performing the garbage collection, or ii) It is possible to determine whether allocations are possible in consideration of at least one of the segments of the memory that have already been vacated among the segments of the memory.

As a result of the determination, the memory controller according to an exemplary embodiment may allocate the chunk to the segment of the empty memory if the segment can be allocated to the segment of the memory in which garbage collection has been performed.

As a result of the determination, if the memory controller can not allocate the segment to the memory, the memory controller may allocate the chunk to a different segment of memory rather than a memory segment corresponding to the object store .

The chunk allocation method according to an embodiment of the present invention minimizes the fragmentation occurring in the memory of the storage device due to the garbage collection by using the unit of the object storage of the host device as a unit of garbage collection.

The chunk allocation method according to an embodiment of the present invention can perform memory management for the heap area of the currently operating processor by performing garbage collection on the memory of the storage device without stopping the processor of the executing host device .

1 is an overall configuration diagram of a host apparatus and a storage apparatus according to an embodiment.
2 is a diagram illustrating a detailed configuration of a heap area of the host apparatus according to one embodiment.
3 is a diagram illustrating a structure of a memory of a storage device corresponding to a heap area of a host apparatus according to an embodiment.
4 is a diagram for explaining an operation of generating an allocation list for a node (chunk) constituting an object repository according to an embodiment.
FIG. 5 is a diagram for explaining an operation for checking whether a chunk allocated to a memory of a storage device is searched for using an allocation list according to an embodiment.
6 is a flowchart illustrating an operation of a host apparatus and a storage apparatus according to an exemplary embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is an overall configuration diagram of a host apparatus and a storage apparatus according to an embodiment.

Referring to FIG. 1, the storage device 101 may use a memory controller 102 for controlling the memory 103 at the request of the host device 104. The memory controller 102 may receive a request from the host device 104 to allocate a chunk to a segment of memory corresponding to the object store of the heap area 105. [ Here, the storage device 101 is a storage medium based on the memory 103. The storage device 101 may be a storage medium based on the memory 103, and may allocate a chunk to a segment of the memory at the request of the host device 104, (GC: Garbage Collection).

For example, the storage device 101 may be a storage medium that allocates a chunk requested from the host device 104 to a segment of memory, or performs garbage collection on a segment of the memory to which the chunk is allocated, and may be a solid state drive (SSD) SOLID STATE DRIVE). In addition, the memory 103 of the storage device 101 may be a non-volatile memory (NVM) in which stored data is not erased even when power is not supplied.

The host device 104 may be a processor on which the program operates. The host device 104 may transmit a request to the storage device 101 to allocate a dynamic memory for the chunk generated in the process of executing the processor.

Here, the heap area 105 may be a virtual memory area used in a processor, and may be a temporary storage space for dynamically allocating memory according to a user's need after program execution (run time). The heap area 105 may be divided into 'object store' units, which are units for performing garbage collection on a segment of memory in which data is actually stored.

More specifically, when garbage collection is performed on the heap area 105, the memories referenced by the objects in the heap area are generally not arranged in order, but are scattered, resulting in fragmentation in the heap area . In order to minimize the fragmentation, compaction is used. However, compaction is not performed in the heap area due to fragmentation of objects. Accordingly, when an allocation request for an object having a large memory use space occurs in the heap area 105 in which the compaction technique is not performed, the host device 104 continuously hops the heap area to allocate the object to the heap area. Collection, resulting in more overhead in program execution time.

In other words, conventionally, when the object space is allocated to the heap area regardless of the storage order and the data space of the heap area is determined as one storage, the full GC overhead due to the lack of space in the heap area occurs when additional objects are allocated The heap area 105 is divided into object storage units for performing garbage collection and objects are allocated to the segments of the memory corresponding to the divided object stores, You can distribute the full GC overhead caused by object allocation.

Here, the object repository of the present invention is an area in which one object is stored, and one object may refer to a data structure for processing or managing considering a relation existing between data. That is, an object store can represent a single data structure. For example, an object repository may contain an object having a data structure such as an array, a linked list, or a tree. The detailed configuration will be described with reference to FIG.

The memory controller 102 may then determine whether a segment of memory corresponding to the object store can be allocated a chunk in response to a request received from the host device 101. [ Here, the chunk may be data stored in each node of the data structure that constitutes the object of the object repository. The segment of the memory may be an area in which data is actually stored corresponding to the storage object area. Each page constituting a segment may be a respective area mapped to store actual data corresponding to each chunk or node constituting a storage object area. The detailed configuration will be described with reference to FIG.

The memory controller 102 may perform garbage collection on the memory using an allocation list if the chunk is not allocatable to a segment of memory. The allocation list may be a list in which the physical addresses of the searched nodes are searched for each node searched in the user data area based on the data structure stored in the metadata area. And, the allocation list can be sorted based on the physical address of the nodes. The operation of generating the allocation list will be described in more detail with reference to FIG.

More specifically, the memory controller 102 may extract an empty segment of a segment of memory to allocate a chunk according to the request to a segment of memory. Here, the empty segment means a page to which a chunk has not yet been allocated among the segment of the memory corresponding to the object store, and can indicate a page in a free state. In addition, the memory controller 102 may merge empty segments, that is, empty segments in a segment of the memory, into one space in order to minimize memory fragmentation.

Thereafter, the memory controller 102 determines whether a segment of memory formed into one space can be allocated a chunk, and if a chunk is not allocated to a segment of memory formed into a space, Can be performed. If the physical address is not found in the allocation list, the memory controller 102 determines that the page of the segment having the non-retrieved physical address is a garbage. If the page determined to be garbage is a page of the memory, You can perform a collection.

The memory controller 102 may then determine whether a segment of the memory in which garbage collection has been performed can be allocated a chunk. In other words, the memory controller 102 may be configured to: i) a segment of memory that has been emptied in the course of performing the garbage collection; or ii) a segment of memory that has not been emptied in the course of performing the garbage collection, It is possible to determine whether or not allocation is possible by taking into account at least one of the segments.

The present invention can perform garbage collection on a segment of a memory depending on whether a chunk is allocated or not. At this time, according to the present invention, a page to be emptied can be generated by performing garbage collection according to whether or not each page constituting a segment of the memory is referred to. In addition, although the present invention performs garbage collection, there may not be a page to be emptied, and there may be a page that has already been emptied and a page that has been emptied by performing garbage collection. Accordingly, the present invention can take each of the above-described states into account when identifying a segment of a memory in which garbage collection has been performed.

The memory controller 102 may allocate the chunk to a segment of the emptied memory if it can be allocated to the segment of the memory in which the garbage collection has been performed as a result of the determination as to whether or not it is allocatable to the segment of the memory in which garbage collection has been performed.

  Conversely, if the memory controller 102 is unable to allocate to a segment of memory for which garbage collection has been performed, the memory controller 102 may allocate the chunk to a segment of memory that is different than a segment of memory corresponding to the object store. At this time, the memory controller can request allocation of a new NVM page through the kernel.

The garbage collection performed in the present invention performs garbage collection on a segment of memory in units of object storage and is not a memory corresponding to the entire heap area but a garbage collection for a segment of memory corresponding to the object storage divided in the heap area It can be referred to as a local garbage collection (LGC), and the local garbage collection can be referred to as a foreground, which is performed when a chunk can not be allocated to a segment of memory in response to a request from the host device, GC.

That is, according to the present invention, a processor executed in a memory controller of a storage device for allocating a memory area to a memory rather than a processor requesting allocation of a chunk to a heap area in the host device operates with high priority, It is possible to perform garbage collection on the memory corresponding to the area.

2 is a diagram illustrating a detailed configuration of a heap area of the host apparatus according to one embodiment.

Referring to FIG. 2, host device 201 may pass a request to a storage device to dynamically allocate a chunk to a segment of memory corresponding to an object store of heap region 202 during execution of the program. Here, the heap area 202 may be divided into units of object repositories 203 and 204 for performing garbage collection. Here, the object repositories 203 and 204 may store one object represented by a silver data structure, and the object repository may be a data structure. At this time, the object repositories 203 and 204 can be divided into a heap area as much as the user wants to use the program.

In other words, the heap area may be divided into object storage units having spaces of different sizes according to the type of the data structure constituting the object repositories (203) and (204). The object stores 203 and 204 are memory areas in which an object having a data structure is stored. Here, the data structure may include basic structures for processing data such as an array, a tree, and a linked list. The object repositories 203 and 204 may store objects of different types according to the characteristics of the data structure.

For example, assuming that the object store 203 stores an object having a data structure of a tree structure and the object store 204 stores an object having a data structure of a linked list, 204 may store objects of different types (tree / linked list).

Accordingly, the object repositories 203 and 204 have different sizes according to the storage structure of the object, and can be dynamically allocated to the heap area in consideration of the size of the object repository.

The object storage 203 may be divided into a metadata area 204 and a user data area 205. In order to allocate a chunk to a nonvolatile memory or to perform garbage collection on a segment of a memory, a chunk allocated to a nonvolatile memory is basically allocated to a nonvolatile memory, It should be checked whether it is referenced by the processor.

Here, the reason for checking whether or not the processor is referenced is that if a chunk allocated to a segment of the current memory is in use by the currently executed processor, and the segment of the memory is deleted because the chunk is not recognized, a fatal error This can happen. In order to check whether the object is referenced, 'type information' and 'pointer position' in which the object allocated in the heap area is recorded are indispensably required.

Accordingly, the present invention can divide the object store 203 into a metadata area 205 and a user data area 205. [ The metadata area 205 may be an area indicating how the data structure of the object of the object repository is implemented, and the user data area 206 may be an area representing the data structure of the object repository 203, It may be an area where processing such as storing and deleting chunks is performed.

As a result, the metadata area 205 is updated by the user when the object store 203 is created in the heap area, and after mapping the object store 203 to the address space of the processor, You can access and use that area.

More specifically, the metadata area 205 proposed by the present invention may be a fixed-size space of about 2 KB (2168 bytes) from the start address of the first segment of the object storage 203. In other words, the start position of the object store 203 may correspond to the start position of the metadata area 205.

Accordingly, in order to access the metadata area 205, a location where the object repository 203 is stored may be searched based on the name of the object repository 203. In this technique, an interface (pos_lookup_mstate (char * name)) for searching the name of each object repository 203 is provided, thereby accessing the metadata area. Also, the metadata area 205 is represented by a data structure called malloc_state, and metadata such as a free chunk list and a prime object (root node) are stored in a fixed size.

As a result, the present invention can find the address of the object store 203 using the name of the object store 203 when assigning / releasing the node to / from the object store, and store the start address of the metadata area 205 in the pointer. Thereafter, the present invention can access the metadata area 205 through the corresponding pointer at any timing, and update metadata such as a free chunk list according to the allocation / release situation.

The heap area 202 may be divided into object storage units according to a request of a user who uses the program, and the object storage may be allocated to heap areas of different types according to a data structure stored in the metadata area.

3 is a diagram illustrating a structure of a memory of a storage device corresponding to a heap area of a host apparatus according to an embodiment.

Referring to FIG. 3, the heap area of the host device 301 may be divided into a plurality of object stores 303 according to the dynamic allocation of the processors. The partitioned object repositories may then be mapped to a memory of the storage device 304. That is, one object store 303 may correspond to one segment 305 of memory, and each node (chunk) that constitutes an object of the object store may be associated with each page 306). That is, the storage device 304 may manage the object store separately in the page 306 of the byte unit constituting the segment 305 of the memory.

In addition, the start position of each node (chunk) constituting the object can be determined by the type information of the data structure indicated by the object in the object store. In other words, you typically use the malloc function to allocate memory dynamically to the heap space, and the prototype of the malloc function can be represented as void * malloc (size_t size). Here, the argument size_t is unsigned int, and only positive numbers can be passed to the storage device. The return type of the malloc function can then be passed as a void * (void point) value. Here, the malloc function uses the address value of the memory segment to access the segment of the memory corresponding to the heap area, and uses a pointer value corresponding to the address value of the memory segment, Can be returned. The host device may then use the memory starting with the address value returned from the storage device.

However, the malloc function manages the free space of the memory, but can not manage the memory area allocated the chunk. This is because it only receives the starting address value for the chunk from the storage device, and then it does not return the address value to access the updated chunk. Accordingly, in the present invention, the following chunk-traversal algorithm can be provided to determine the location where each chunk is stored corresponding to each data structure represented by the object of the object store.

The chunk traversal algorithm can identify the start address of each chunk by adding space occupied by the metadata region to the address of the first page of the segment of memory in response to the object store. In other words, the chunk traversal algorithm is an algorithm that checks the address of the next chunk by adding the size of each chunk to the address of the first page of the segment of memory.

More specifically, the object store can be broken down into multiple chunked units by the memory allocator and presented to the user. Here, the chunk traversal algorithm is an algorithm designed to check all the chunks and to find a space accessible at the system level. That is, the chunk traversal algorithm can check all chunks (accessible chunks being allocated) that are not free chunks from the highest to the last chunk on the address. The chunk may be allocated from the space immediately following the metadata area to the structure shown in FIG. 7 below. Referring to FIG. 7, one chunk may be composed of size metadata for storing its size and a space for storing actual data. However, see the actual chunk in Fig. prev_size, fd, bk, etc. are created when chunks become free chunks and may not be used normally.

Thus, chunks can be traversed by finding the next chunk by adding the size of the space from the beginning of the chunk. Then, the address of the chunk at the starting location can be found by adding the size of the metadata area (fixed size) to the starting address of the object store, and the chunk to be looked for next can be found by adding the size to the starting chunk have. The chunk allocation can be checked by checking the p bits of the next chunk.

Here, the p bit is a prev_inuse bit and may be a bit indicating whether or not the immediately preceding chunk is allocated. Therefore, whether or not the current chunk is allocated can be determined by checking the p bit of the next chunk. In this way, you can check whether all chunks are allocated by traversing to the last chunk.

Also, according to the present invention, it is possible to check whether a chunk allocated to a segment of a memory is referred to by checking all the chunks in one segment through such a method, determine chunks allocated to the segment as garbage according to whether to check, It is possible to perform garbage collection on the memory targeted at the chunks judged as < RTI ID = 0.0 > The detailed configuration will be described with reference to FIGS. 4 to 5. FIG.

4 is a diagram for explaining an operation of generating an allocation list for a node (chunk) constituting an object storage according to an embodiment.

In the present invention, the assignment list on the current implementation can be generated by the garbage collector library. In other words, in the implemented technique, the host and the storage device (hardware) only provide abstraction on a page basis, but do not care about the allocation of the units below. Therefore, the memory allocator is responsible for dividing and providing chunks, and this technique also operates on the abstraction. In other words, at the system level, the memory space of a page unit is provided to the library through a system call, and this library can divide the page unit space into chunk units and provide it to the user.

Referring to FIG. 4, when a user receives a request to allocate a chunk to an object store, the memory controller of the storage device can check whether or not the corresponding chunk can be allocated to a segment of the memory. At this time, the memory controller can check all the chunks allocated pages and chunks assigned thereto while traversing all of the chunks in the segment. To this end, the memory controller can utilize an allocation list for the object store.

The allocation list may include a physical address corresponding to a chunk allocated to an object store of the heap area based on a data structure stored in the metadata area. Specifically, the host device can generate an allocation list of physical addresses of nodes to be searched by traversing the data structure of the object store based on the root node (prime chunk) among the nodes constituting the object at the object location. The host device can sort the created allocation list based on the physical addresses of the nodes.

Here, the reason why the allocation list is sorted by the physical addresses of the nodes is that the garbage included in the segments of the memory is retrieved faster by considering whether or not memory is allocated to the nodes allocated to the object store, It may be for quick creation. 3, the size of each chunk is added to the address of the first page of the segment in order to determine the position where each chunk is stored corresponding to each data structure, You can see the address of the chunk. Therefore, the present invention can arrange allocation lists in order of physical addresses of the data structures so that garbage can be detected in the memory by only one round trip.

Since the metadata storage area of the object repository can know which object structure is constituted by a data structure, it is possible to select a search algorithm and search for each node through a search algorithm.

In the metadata (descriptor) representing the object store, the data structure type to be stored by the user can be stored as a 4-byte number. For this purpose, this technique provides an interface that can store the data structure type when creating the object repository. In more detail, the member field obj_storage_type in the descriptor is a variable that stores the data structure type of the object store. If the user wants to collect garbage, the data structure type to be stored in the object store must be stored in this member field.

To do this, this technique provides an interface (system call) that stores the data type in obj_storage_type. These interfaces are sys_pos_set_storage_type () / sys_pos_get_storage_type (), respectively, and distinguish types by values stored in the obj_storage_type field. For example, if the value stored in the obj_storage_type field is '0', it is a linked list. If the value stored in the obj_storage_type field is '1', it is a b-tree.

The present invention basically provides a search algorithm for the above three data structures, provides a header file for a user to input a search algorithm for a user-defined data structure, and inserts a search algorithm code This allows garbage collection of the data structure. Also, at garbage collection, it is possible to determine which data structure is stored based on the value stored in obj_storage_type, and then apply a search algorithm to the data structure.

FIG. 5 is a diagram for explaining an operation for checking whether a chunk allocated to a memory of a storage device is searched for using an allocation list according to an embodiment.

Referring to FIG. 5, the memory controller can determine whether a chunk can be allocated to a segment of the memory 501 corresponding to the object store according to a request received from the host device. If the memory controller is not allocatable to a segment of the memory 501, it can perform garbage collection on a segment of the memory 501 using the allocation list 502. [

Here, the memory controller can confirm whether or not each of the chunks 503, 504, and 505 allocated to the segment of the memory 501 is referenced to the host device using the allocation list 502. [ In other words, if the chunk allocated to the segment of memory 501 is not retrieved from the allocation list 502, then the memory controller determines that the chunk 503, 504, 505 is not referenced in the host device And may be disconnected and disconnected from a segment of memory as the host device no longer uses the chunk. Accordingly, the memory controller can determine garbage as a segment to which a chunk has not been searched in the allocation list 502, and perform garbage collection on the segment determined to be garbage.

Here, since the allocation list 502 is arranged in addresses related to the segment of the memory, each node of the object and the segments of the memory have a one-to-one correspondence relationship, so that 1: 1 comparison is possible. Therefore, the present invention can detect a chunk judged to be garbage by only one round without searching several times.

For example, as shown in FIG. 5, the present invention may be such that original chunks are allocated to the rest of the physical addresses Ox100 to Ox150 of the memory of the storage device except the Ox 130 address. In other words, the page of the segment having the Ox130 address is empty, and the pages of the segment having the remaining address may be in a state where the chunk is stored. Then, the memory controller can determine that Ox 110 and Ox 150 are not searched in the allocation list by performing a 1: 1 comparison between the allocation list and the memory in order to allocate chunks. Then, the memory controller can judge a page having addresses Ox110 and Ox150 that are not searched in the allocation list as garbage, and perform garbage collection on the pages (Ox110 and Ox150) judged as garbage.

Therefore, according to the present invention, not only a segment emptied in a segment of a memory but also a reference to a processor are checked, and a garbage collection of a segment of a memory judged as a garbage is performed according to a result of checking, , The segment of memory corresponding to the object store of the heap area can be more efficiently managed.

6 is a flowchart illustrating an operation of a host apparatus and a storage apparatus according to an exemplary embodiment of the present invention.

In step 601, the host device 104 may pass a request to the memory controller of the storage device to allocate a chunk to a segment of memory corresponding to the object store of the heap area.

In step 602, the memory controller 102 may determine whether the requested chunk is allocable to a segment of memory according to a request received from the host device. Specifically, the memory controller can determine whether a segment of the memory is empty, and determine whether a chunk can be allocated to the identified empty segment. At this time, the memory controller merges and manages the empty segments of the segments of the memory into one space, so that the memory fragmentation phenomenon can be minimized.

If the allocation to the segment of the memory is not possible (No), in step 603, the memory controller 102 can perform garbage collection on the memory using the allocation list (allocation list).

In step 604, the memory controller 102 may re-verify whether or not it is able to allocate a chunk to a segment of memory that has garbage collected. In other words, according to the present invention, a memory in which garbage collection is performed for performing garbage collection on a memory depending on whether or not a chunk is allocated may have a segment of a memory determined as garbage depending on whether the memory is referenced to the host device. Then, the memory controller 102 can perform garbage collection on the determined segment of the memory, thereby confirming whether the chunk is allocated through the empty segment through garbage collection.

Here, in order to minimize memory fragmentation, the memory controller 102 may merge empty segments, that is, empty segments, into a single space. In other words, the memory controller merely merges segments of memory that have been previously empty before performing garbage collection according to a situation, as well as a segment of memory that has been emptied in the process of performing garbage collection, It is possible to reconfirm whether or not a chunk is allocated to the formed segment.

If it is possible to allocate a chunk to a segment that has been emptied through garbage collection (Yes), then at step 605 the memory controller 102 may allocate a chunk to the emptied segment via garbage collection.

In addition, the memory controller may allocate a chunk to an empty segment of a segment of memory corresponding to the object store, even if it is determined to be 'Yes' at step 602. In this case, it may be a segment that is empty regardless of garbage collection.

In step 606, the memory controller 102 may return the physical address value of the chunk allocated to the segment of the emptied memory to the host device.

If the allocation of chunks to the emptied segment is not possible (No), then in step 607 the memory controller 102 allocates the chunks to segments of different memory rather than a segment of memory corresponding to the object store The memory controller 102 may request a new page to allocate a chunk through the kernel and allocate that chunk to a page of a new segment according to the request.

In step 608, the memory controller 102 may return the physical address value of the chunk assigned to the segment of memory to the host device.

In step 609, the host device 104 may use the chunk allocated to the memory from the memory controller.

The present invention can propose a technique for enabling garbage collection for various types of user objects by storing type information (data structure) of objects in the NVM-based system as metadata and storing them in the object store.

The methods according to embodiments of the present invention may be implemented in the form of program instructions that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions recorded on the medium may be those specially designed and configured for the present invention or may be available to those skilled in the art of computer software.

While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. This is possible.

Therefore, the scope of the present invention should not be limited to the described embodiments, but should be determined by the equivalents of the claims, as well as the claims.

101: Storage device
102: Memory controller
103: Storage memory
104: Host device
105: Heap area

Claims (18)

A chunk allocation method performed by a memory controller of a storage device,
Receiving a request from a host device to allocate a chunk to a segment of memory corresponding to an object store of the heap area;
Determining whether the chunk is allocatable to a segment of memory in response to the received request;
Performing garbage collection on a segment of memory using an allocation list if the chunk is not allocatable to a segment of the memory;
Determining whether the chunk is allocable to a segment of memory in which garbage collection has been performed; And
Assigning the chunk to a segment of memory according to a determination result
/ RTI > The method according to claim 1,
Wherein determining whether allocation to the segment of memory is possible comprises:
And determining whether the chunk is allocated to an empty segment of a segment of memory corresponding to the object store. The method according to claim 1,
The step of performing the garbage collection includes:
And performing garbage collection in consideration of whether a physical address indicating pages constituting a segment of the memory is retrieved from the allocation list. The method of claim 3,
The step of performing the garbage collection includes:
A chunk for judging a page of a segment having the physical address not to be retrieved as garbage when the physical address is not retrieved from the allocation list and a chunk for performing garbage collection on a segment of the memory, Assignment method. The method according to claim 1,
The object repository,
A metadata area for storing a type of a data structure for allocating a chunk to a segment of the memory, and a user data area for storing data,
The heap region may include:
And allocating the chunks in units of the object store. 6. The method of claim 5,
The allocation list includes:
And searching for each node retrieved in the user data area based on a data structure stored in the metadata area and including physical addresses of the retrieved nodes,
Wherein the chunks are allocated based on physical addresses of the nodes. The method according to claim 1,
Wherein the step of determining whether the segment of the memory in which the garbage collection has been performed is allocatable,
i) a segment of memory that has been flushed in the course of performing the garbage collection, or
ii) a segment of the memory is not emptied in the process of performing the garbage collection, but a segment of the memory,
And determining whether or not allocation is possible. 8. The method of claim 7,
The step of allocating the chunk comprises:
And allocating the chunk to the segment of the empty memory if the segment of the memory in which the garbage collection is performed can be allocated. 8. The method of claim 7,
The step of allocating the chunk comprises:
And allocating the chunks to segments of different memory rather than segments of the memory corresponding to the object store if the allocation of segments to the memory in which garbage collection has been performed is not possible. A memory controller for performing a chunk allocation method,
The memory controller includes:
Upon receipt of a request from a host device to allocate a chunk to a segment of memory corresponding to an object store of the heap area, determines whether the chunk is allocatable to a segment of memory in response to the received request, If it is impossible to allocate the chunk to a segment of the memory, after performing garbage collection on a segment of memory using an allocation list (allocation list), it is determined whether or not the chunk can be allocated to a segment of the memory on which garbage collection has been performed And allocates the chunk to a segment of the memory in accordance with the determination result. 11. The method of claim 10,
The memory controller includes:
Wherein the memory controller determines whether the chunk is allocated to an empty segment of a segment of memory corresponding to the object store. 11. The method of claim 10,
The memory controller includes:
Wherein the memory controller performs garbage collection in consideration of whether or not a physical address indicating pages constituting a segment of the memory is retrieved from the allocation list. 13. The method of claim 12,
The memory controller includes:
A page of a segment having a physical address not to be retrieved is judged as a garbage when the physical address is not retrieved from the allocation list, and a storage for performing garbage collection of a segment of a memory as a target page of the garbage The device's memory controller. 11. The method of claim 10,
The object repository,
A metadata area for storing a type of a data structure for allocating a chunk to a segment of the memory, and a user data area for storing data,
The heap region may include:
The memory controller of the storage device being divided into units of the object store. 15. The method of claim 14,
The allocation list includes:
And searching for each node retrieved in the user data area based on a data structure stored in the metadata area and including physical addresses of the retrieved nodes,
And the physical addresses of the nodes. 11. The method of claim 10,
Wherein the step of determining whether the segment of the memory in which the garbage collection has been performed is allocatable,
i) a segment of memory that has been flushed in the course of performing the garbage collection, or
ii) a segment of the memory is not emptied in the process of performing the garbage collection, but a segment of the memory,
And determines whether or not allocation is possible. 17. The method of claim 16,
The memory controller includes:
Wherein the memory controller allocates the chunk to the segment of the empty memory when the segment is allocated to the segment of the memory in which garbage collection has been performed. 11. The method of claim 10,
The memory controller includes:
Wherein the memory controller allocates the chunks to segments of memory that are different from segments of the memory corresponding to the object store when the segments can not be allocated to the segments of the memory in which garbage collection has been performed.

Images