Memory apparatus for in-place regular expression search

• US 10,282,436 B2
• Filed: 03/27/2017
• Issued: 05/07/2019
• Est. Priority Date: 01/04/2017
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Malladi, Krishna T., Zheng, Hongzhong
• Primary Examiner(s): Mercado, Ramon A.
• Application Number:
  US15/470,709
• Publication Number:
  US 20180188968A1
• Time in Patent Office: 771 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A method of searching for data stored in a memory, the method including receiving a regex search request, generating a parse tree including fundamental regex operations corresponding to the regex search request, individually analyzing each of the fundamental regex operations of the generated parse tree in a respective time-step, determining a memory address location of data corresponding to the analyzed fundamental regex operations by using a translation table to determine whether the data exists, and using a reverse translation table to determine the memory address location of the data, and outputting data matching the regex search request after analyzing all of the fundamental regex operations of the generated parse tree.

Claims

1. A method of searching for data stored in a memory, the method comprising:

receiving a regex search request;

generating a parse tree comprising fundamental regex operations corresponding to the regex search request;

individually analyzing each of the fundamental regex operations of the generated parse tree in a respective time-step;

determining a memory address location of data corresponding to the analyzed fundamental regex operations by;

using a translation table to determine whether the data exists; and

using a reverse translation table to determine the memory address location of the data, the data being stored in a deduplicated format;

outputting data matching the regex search request after analyzing all of the fundamental regex operations of the generated parse tree;

setting a minimum substring match ability;

providing a rolling window covering a portion of a searched pattern corresponding to the regex search request; and

upon finding a match within the rolling window, searching for data having an address location immediately prior to or immediately subsequent to an address location of data corresponding to the match within the rolling window.

2. The method of claim 1, further comprising using logic gates to process the fundamental regex operations, wherein the fundamental regex operations comprise at least one of a concatenation operation, an or operation, a closure operation, or a parenthesis operation.

3. The method of claim 1, wherein receiving the regex search request comprises receiving the regex search request at a computer application.

4. The method of claim 1, wherein generating the parse tree comprising the fundamental regex operations comprises:

receiving the regex search request at a driver; and

using the driver to generate the parse tree.

5. The method of claim 1, wherein outputting the data matching the regex search request comprises generating a value and address location corresponding to the data.

6. The method of claim 1, wherein determining the memory address location of data corresponding to the analyzed fundamental regex operations comprises:

using a pointer to indicate a starting memory address of the data; and

using a counter to indicate a number of memory addresses from the starting memory address having the data.

7. The method of claim 1, further comprising storing the data in the deduplicated format, wherein a same logic is used for storing the data and for generating the parse tree.

8. A system for searching for data stored in a memory, the system comprising:

a processor of a regex module configured to communicate with a host CPU; and

a memory having instructions stored thereon that, when executed by the processor, cause the processor to;

receive a regex search request;

generate a parse tree comprising fundamental regex operations corresponding to the regex search request;

individually analyze each of the fundamental regex operations of the generated parse tree in a respective time-step;

determine a memory address location of data corresponding to the analyzed fundamental regex operations by;

using a pointer to indicate a starting memory address of the data;

using a counter to indicate a number of memory addresses from the starting memory address having the data;

using a bit vector for storing matches; and

eliminating non-matches at each of a plurality of time-steps using logic implementation; and

output data matching the regex search request after all of the fundamental regex operations of the generated parse tree are analyzed.

9. The system of claim 8, further comprising logic gates configured to process the fundamental regex operations, wherein the fundamental regex operations comprise at least one of a concatenation operation, an or operation, a closure operation, or a parenthesis operation.

10. The system of claim 8, wherein the instructions, when executed by the processor, cause the processor to receive the regex search request by receiving the regex search request at a computer application.

11. The system of claim 8, wherein the instructions, when executed by the processor, cause the processor to generate the parse tree comprising the fundamental regex operations by:

receiving the regex search request at a driver; and

using the driver to generate the parse tree.

12. The system of claim 8, wherein the instructions, when executed by the processor, cause the processor to determine a memory address location of the data corresponding to the analyzed fundamental regex operations by:

using a translation table to determine whether the data exists; and

using a reverse translation table to determine the memory address location of the data.

13. The system of claim 8, wherein the instructions, when executed by the processor, cause the processor to output the data matching the regex search request by generating a value and address location corresponding to the data.

14. A system for searching for data stored in a memory of a memory module, the system comprising:

an application configured to receive a regex search request;

a driver configured to generate a parse tree comprising fundamental regex operations corresponding to the regex search request; and

a regex module configured to;

individually analyze each of the fundamental regex operations of the generated parse tree in a respective time-step;

determine a memory address location of data corresponding to the analyzed fundamental regex operations;

set a minimum substring match ability;

provide a rolling window covering a portion of a searched pattern corresponding to the regex search request; and

upon finding a match within the rolling window, search for data having an address location immediately prior to or immediately subsequent to an address location of data corresponding to the match within the rolling window,

wherein the application is further configured to output data matching the regex search request after all of the fundamental regex operations of the generated parse tree are analyzed.

15. The system of claim 14, wherein the fundamental regex operations comprise at least one of a concatenation operation, an or operation, a closure operation, or a parenthesis operation.

16. The system of claim 14, wherein the driver is configured to generate the parse tree comprising the fundamental regex operations after receiving the regex search request from the application.

17. The system of claim 14, wherein the regex module is configured to determine the memory address location of the data corresponding to the analyzed fundamental regex operations by:

using a translation table to determine whether the data exists; and

using a reverse translation table to determine the memory address location of the data.

18. The system of claim 14, wherein the regex module is configured to determine the memory address location of the data corresponding to the analyzed fundamental regex operations by:

using a pointer to indicate a starting memory address of the data; and

using a counter to indicate a number of memory addresses from the starting memory address having the data.

19. The system of claim 14, wherein the application is configured to output the data matching the regex search request by receiving a value and address location corresponding to the data from the regex module.

20. The system of claim 14, wherein the regex module is located on the memory module.