Patent ID: 8745313

Claim:
A memory system comprising: a nonvolatile semiconductor memory including a plurality of blocks, each one of the plurality of blocks being a data erasing unit and being capable of storing N pieces of valid data, valid data being managed by a size of a management unit, the size of the management unit being larger than a size of one page which is a writing unit for the nonvolatile semiconductor memory, and being smaller than a size of one block; a volatile semiconductor memory including a storage area; and a controller configured to: manage the plurality of blocks in a plurality of linked lists, each one of the plurality of linked lists linking blocks with a same number of valid data, a first linked list managing blocks with a first number of valid data and a second linked list managing blocks with a second number of valid data, the first number being smaller than the second number, the first and second numbers being selected from among numbers of 1 to N−1; retrieve compaction source blocks from among the blocks managed by the first linked list, and if there are no blocks managed by the first linked list, thereafter retrieving the compaction source blocks from among the blocks managed by the second linked list; select valid data stored in the compaction source blocks, rewrite the selected valid data in a first compaction target block different from the compaction source blocks, and release the compaction source blocks after rewriting the selected valid data; and store write data in the storage area, the write data being sent from a host apparatus, wherein when the sum of valid data included in the compaction source blocks reaches a size of one block, the controller is configured to acquire the first compaction target block and rewrite the selected valid data in the first compaction target block, when the sum of valid data included in the compaction source blocks does not reach a size of one block, the controller is configured to rewrite the selected valid data in a block allocated to an input buffer of the nonvolatile semiconductor memory as a first valid data, when the write data stored in the storage area reaches the size of the management unit, the controller is configured to copy the write data stored in the storage area to the input buffer as a second valid data, and when a total size of the first and second valid data included in the input buffer reaches a size of one block, the controller is configured to rewrite the first and second valid data included in the input buffer in a second compaction target block, and release the block allocated to the input buffer after rewriting the first and second valid data included in the input buffer.