Skip to contentSkip to conversation

parsing_c: Optimize recursive header file parsing

PATCH Applied Jaskaran Singh 2 participants 6 messages Sep 10, 2020 – Sep 15, 2020 Kbuild

lore
Share & tools
lore
#0 lore raw

v2 cover parsing_c: Optimize recursive header file parsing

This patch series aims to optimize performance for recursively parsing header files in Coccinelle.

Coccinelle's C parsing subsystem has an option called --recursive-includes to recursively parse header files. This is used for type inference/annotation.

Previously, using --recursive-includes on the entire Linux kernel source code would take far too long. On my computer with the following specs,
- Processor: AMD Ryzen 5 3550H
- RAM: 8 GB
it would take close to 7 hours to complete. The optimization that this patch series implements reduces that time to 1 hour.

The following is a high-level description of what has been implemented:
- As header files are recursively parsed, they are scanned for the following:
- fields of structs/unions/enums
- typedefs
- function prototypes
- global variables
The names of the above are stored in a "name cache", i.e. a hashtable to map the name to the files it is declared in.
- A dependency graph is built to determine dependencies between all the files in the codebase.
- In the type annotation phase of the C subsystem, if a function call, struct/union field or identifier is encountered, the type of which is not known to the annoter, the name cache is checked for the name.
- The name cache gives a list of files that the name is declared/defined in. These files are cross checked with the dependency graph to determine if any of these are reachable by the file that the annoter is working on.
- If a reachable header file is found, that file is parsed and the type associated to the name is returned.

Different approaches that were attempted to alleviate this issue, and the problems with each are as follows:
- Caching the most recently used files: A LRU cache to store ASTs of the most recently encountered header files. The problem with this approach is the amount of memory it takes to cache the header file ASTs.
- Caching the most troublesome files: A pseudo-LFU cache to store files that cumulatively take the longest to parse, and thus bloat the time taken. The problem with this approach is the amount of memory it takes to cache the header file ASTs.
- Skipping unparsable locations in header files: Skipping top-level items in a header file that cannot be parsed. This approach does not produce even close to the amount of optimization needed.

The next step from here would be:
- Maintain a small but persistent cache of header files in groups of directories. Leverage multiprocessing for parsing these header files.
- Leverage multiprocessing to parse header files initially for name extraction.
- Performing some initial matching with the semantic patch to determine if a C file matches. If matches are found, call the annoter and recursively parse header files for type annotation.
- Recursively parse all header files only once and build a large type environment. Use the dependency graph to determine reachability. This has potential memory usage issues though.

Changes in v2:
--------------
- Change occurences of 'begin' and 'match' on the same line with something else to the next line for better readability.

 Makefile                     |    2 
 parsing_c/includes_cache.ml  |  286 +++++++++++++++++++++++++++++++++++++++++++
 parsing_c/includes_cache.mli |   47 +++++++
 parsing_c/parse_c.ml         |   27 +++-
 parsing_c/type_annoter_c.ml  |  130 ++++++++++++++++---
 5 files changed, 466 insertions(+), 26 deletions(-)

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci

#1 lore raw

PATCH v2 1/3 parsing_c: includes_cache: Implement a name cache

Implement a name cache and includes dependency graph to optimize performance for recursive parsing of header files.

The following is a high-level description of what has been implemented:
- As header files are recursively parsed, they are scanned for the following:
- fields of structs/unions/enums
- typedefs
- function prototypes
- global variables
The names of the above are stored in a "name cache", i.e. a hashtable to map the name to the files it is declared in.
- A dependency graph is built to determine dependencies between all the files in the codebase.
- In the type annotation phase of the C subsystem, if a function call, struct/union field or identifier is encountered, the type of which is not known to the annoter, the name cache is checked for the name.
- The name cache gives a list of files that the name is declared/defined in. These files are cross checked with the dependency graph to determine if any of these are reachable by the file that the annoter is working on.
- If a reachable header file is found, that file is parsed and all of the above listed constructs are extracted from it.

---
 Makefile                     |   2 +-
 parsing_c/includes_cache.ml  | 290 +++++++++++++++++++++++++++++++++++
 parsing_c/includes_cache.mli |  47 ++++++
 3 files changed, 338 insertions(+), 1 deletion(-)
 create mode 100644 parsing_c/includes_cache.ml
 create mode 100644 parsing_c/includes_cache.mli
Makefile +1 -1
index e25174413..f8d3424c0 100644
@@ -50,7 +50,7 @@ SOURCES_parsing_cocci := \
 SOURCES_parsing_c := \
 	token_annot.ml flag_parsing_c.ml parsing_stat.ml \
 	token_c.ml ast_c.ml includes.ml control_flow_c.ml \
-	visitor_c.ml lib_parsing_c.ml control_flow_c_build.ml \
+	visitor_c.ml lib_parsing_c.ml includes_cache.ml control_flow_c_build.ml \
 	pretty_print_c.ml semantic_c.ml lexer_parser.ml parser_c.mly \
 	lexer_c.mll parse_string_c.ml token_helpers.ml token_views_c.ml \
 	cpp_token_c.ml parsing_hacks.ml cpp_analysis_c.ml \
parsing_c/includes_cache.ml new file +290 -0

290 lines not on this page · raw message

parsing_c/includes_cache.mli new file +47 -0

47 lines not on this page · raw message

Signature · 6 lines
2.21.3

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci
#2 lore raw

PATCH v2 2/3 parsing_c: parse_c: Build name cache and includes dependency graph

In reply to Jaskaran Singh

Build the includes dependency graph and name cache while parsing header files. Every header file is parsed only once for name caching and, while parsing these files, an includes dependency graph is built to determine reachability of one header file from another file.

---
 parsing_c/parse_c.ml | 28 ++++++++++++++++++++++------
 1 file changed, 22 insertions(+), 6 deletions(-)
parsing_c/parse_c.ml +22 -6
index 5574cb11b..ef5870123 100644
@@ -17,6 +17,7 @@ open Common
 
 module TH = Token_helpers
 module LP = Lexer_parser
+module IC = Includes_cache
 
 module Stat = Parsing_stat
 
@@ -995,15 +996,30 @@ let rec _parse_print_error_heuristic2 saved_typedefs saved_macros
 and handle_include file wrapped_incl k =
     let incl = Ast_c.unwrap wrapped_incl.Ast_c.i_include in
     let parsing_style = Includes.get_parsing_style () in
+    let f = Includes.resolve file parsing_style incl in
     if Includes.should_parse parsing_style file incl
     then
-      match Includes.resolve file parsing_style incl with
+      match f with
       | Some header_filename when Common.lfile_exists header_filename ->
-	  (if !Flag_parsing_c.verbose_includes
-	  then pr2 ("including "^header_filename));
-	  let nonlocal =
-	    match incl with Ast_c.NonLocal _ -> true | _ -> false in
-          ignore (k nonlocal header_filename)
+          if not (IC.has_been_parsed header_filename)
+          then
+            begin
+              IC.add_to_parsed_files header_filename;
+              (if !Flag_parsing_c.verbose_includes
+              then pr2 ("including "^header_filename));
+              let nonlocal =
+                match incl with Ast_c.NonLocal _ -> true | _ -> false in
+              let res = k nonlocal header_filename in
+              match res with
+                None -> ()
+              | Some x ->
+                  let pt = x.parse_trees in
+                  let (p, _, _) = pt in
+                  with_program2_unit
+                    (IC.extract_names header_filename)
+                    p
+            end;
+          IC.add_to_dependency_graph file header_filename;
       | _ -> ()
 
 and _parse_print_error_heuristic2bis saved_typedefs saved_macros
Signature · 6 lines
2.21.3

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci
#3 lore raw

PATCH v2 3/3 parsing_c: type_annoter_c: Use name cache for type annotation

In reply to Jaskaran Singh

Use the name cache for type annotation. On encountering the following which are not stored in the environment, the name cache is looked up and the relevant header file is parsed for type information:
- struct field use
- typedef
- function call
- identifier
- enumeration constant

---
 parsing_c/type_annoter_c.ml | 134 +++++++++++++++++++++++++++++++-----
 1 file changed, 115 insertions(+), 19 deletions(-)
parsing_c/type_annoter_c.ml +115 -19
index 25cb6c0ee..49fd060be 100644
@@ -19,6 +19,7 @@ open Common
 open Ast_c
 
 module Lib = Lib_parsing_c
+module IC = Includes_cache
 
 (*****************************************************************************)
 (* Prelude *)
@@ -186,6 +187,13 @@ type nameenv = {
 
 type environment = nameenv list
 
+let includes_parse_fn file =
+  let choose_includes = Includes.get_parsing_style () in
+  Includes.set_parsing_style Includes.Parse_no_includes;
+  let ret = Parse_c.parse_c_and_cpp false false file in
+  Includes.set_parsing_style choose_includes;
+  List.map fst (fst ret)
+
 (* ------------------------------------------------------------ *)
 (* can be modified by the init_env function below, by
  * the file environment_unix.h
@@ -294,6 +302,39 @@ let member_env_lookup_enum s env =
   | [] -> false
   | env :: _ -> StringMap.mem s env.enum_constant
 
+(* ------------------------------------------------------------ *)
+
+let add_cache_binding_in_scope namedef =
+  let (current, older) = Common.uncons !_scoped_env in
+  let new_frame fr =
+    match namedef with
+      | IC.RetVarOrFunc (s, typ) ->
+	  {fr with
+	   var_or_func = StringMap.add s typ fr.var_or_func}
+      | IC.RetTypeDef   (s, typ) ->
+	  let cv = typ, fr.typedef, fr.level in
+	  let new_typedef_c : typedefs = { defs = StringMap.add s cv fr.typedef.defs } in
+	  {fr with typedef = new_typedef_c}
+      | IC.RetStructUnionNameDef (s, (su, typ)) ->
+	  {fr with
+	   struct_union_name_def = StringMap.add s (su, typ) fr.struct_union_name_def}
+      | IC.RetEnumConstant (s, body) ->
+	  {fr with
+	   enum_constant = StringMap.add s body fr.enum_constant} in
+  (* These are global, so have to reflect them in all the frames. *)
+  _scoped_env := (new_frame current)::(List.map new_frame older)
+
+(* Has side-effects on the environment.
+ * TODO: profile? *)
+let get_type_from_includes_cache file name exp_types on_success on_failure =
+  let file_bindings =
+    IC.get_types_from_name_cache
+      file name exp_types includes_parse_fn in
+  List.iter add_cache_binding_in_scope file_bindings;
+  match file_bindings with
+    [] -> on_failure ()
+  | _ -> on_success ()
+
 
 (*****************************************************************************)
 (* "type-lookup"  *)
@@ -394,7 +435,14 @@ let rec type_unfold_one_step ty env =
 	  then type_unfold_one_step t' env'
           else loop (s::seen) t' env
        with Not_found ->
-          ty
+          let f = Ast_c.file_of_info (Ast_c.info_of_name name) in
+          get_type_from_includes_cache
+            f s [IC.CacheTypedef]
+            (fun () ->
+              let (t', env') = lookup_typedef s !_scoped_env in
+              TypeName (name, Some t') +>
+              Ast_c.rewrap_typeC ty)
+            (fun () -> ty)
       )
 
   | FieldType (t, _, _) -> type_unfold_one_step t env
@@ -474,7 +522,15 @@ let rec typedef_fix ty env =
 	      TypeName (name, Some fixed) +>
 	      Ast_c.rewrap_typeC ty
             with Not_found ->
-              ty))
+              let f = Ast_c.file_of_info (Ast_c.info_of_name name) in
+              get_type_from_includes_cache
+                f s [IC.CacheTypedef]
+                (fun () ->
+                   let (t', env') = lookup_typedef s !_scoped_env in
+                   TypeName (name, Some t') +>
+                   Ast_c.rewrap_typeC ty)
+                (fun () -> ty)
+              ))
 
     | FieldType (t, a, b) ->
 	FieldType (typedef_fix t env, a, b) +> Ast_c.rewrap_typeC ty
@@ -797,8 +853,16 @@ let annotater_expr_visitor_subpart = (fun (k,bigf) expr ->
                     Type_c.noTypeHere
                 )
             | None ->
-                pr2_once ("type_annotater: no type for function ident: " ^ s);
-                Type_c.noTypeHere
+                let f =
+                  Ast_c.file_of_info
+                    (Ast_c.info_of_name ident) in
+                get_type_from_includes_cache
+                  f s [IC.CacheVarFunc]
+                  (fun () ->
+                     match lookup_opt_env lookup_var s with
+                       Some (typ, local) -> make_info_fix (typ, local)
+                     | None -> Type_c.noTypeHere)
+                  (fun () -> Type_c.noTypeHere)
             )
         )
 
@@ -848,22 +912,36 @@ let annotater_expr_visitor_subpart = (fun (k,bigf) expr ->
                 | Some _ ->
                     make_info_def (type_of_s "int")
                 | None ->
-                    if not (s =~ "[A-Z_]+") (* if macro then no warning *)
-                    then
-                      if !Flag_parsing_c.check_annotater then
-                        if not (Hashtbl.mem _notyped_var s)
-                        then begin
-                          pr2 ("Type_annoter: no type found for: " ^ s);
-                          Hashtbl.add _notyped_var s true;
-                        end
-                        else ()
-                      else
-                        pr2 ("Type_annoter: no type found for: " ^ s)
-                    ;
-                    Type_c.noTypeHere
-                )
+                    let f = Ast_c.file_of_info (Ast_c.info_of_name ident) in
+                    let failure_fn =
+                      (fun () ->
+                         if not (s =~ "[A-Z_]+") (* if macro then no warning *)
+                         then
+                           if !Flag_parsing_c.check_annotater
+                           then
+                             if not (Hashtbl.mem _notyped_var s)
+                             then
+                               begin
+                                 pr2
+                                   ("Type_annoter: no type found for: " ^ s);
+                                 Hashtbl.add _notyped_var s true;
+                               end
+                             else ()
+                           else pr2 ("Type_annoter: no type found for: " ^ s);
+                         Type_c.noTypeHere) in
+                    get_type_from_includes_cache
+                      f s [IC.CacheEnumConst;IC.CacheVarFunc]
+                      (fun () ->
+                         match lookup_opt_env lookup_enum s with
+                           Some _ -> make_info_def (type_of_s "int")
+                         | None ->
+                             (match lookup_opt_env lookup_var s with
+                                Some (typ,local) -> make_info_fix (typ,local)
+                              | None -> failure_fn ()))
+                      failure_fn
             )
         )
+    )
 
     (* -------------------------------------------------- *)
     (* C isomorphism on type on array and pointers *)
@@ -954,7 +1032,25 @@ let annotater_expr_visitor_subpart = (fun (k,bigf) expr ->
                         Type_c.noTypeHere
                   )
               | _ ->
-		  Type_c.noTypeHere
+                let s = Ast_c.str_of_name namefld in
+                let f = Ast_c.file_of_info (Ast_c.info_of_name namefld) in
+                let ret_typ =
+                  (match (Ast_c.unwrap (snd t)) with
+                    Ast_c.StructUnionName(su, sname) ->
+                      get_type_from_includes_cache
+                        f s [IC.CacheField sname]
+                        (fun () ->
+                           try
+                             let ((su,fields),ii) =
+                               lookup_structunion (su, sname) !_scoped_env in
+                               try
+                                  make_info_def_fix
+                                    (Type_c.type_field fld (su, fields))
+                                with _ -> Type_c.noTypeHere
+                           with Not_found -> Type_c.noTypeHere)
+                        (fun () -> Type_c.noTypeHere)
+                  | _ -> Type_c.noTypeHere)
+                in ret_typ
           )
         )
 
Signature · 6 lines
2.21.3

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci
#4 lore raw
In reply to Jaskaran Singh
Quoted 93 lines · Jaskaran Singh

This patch series aims to optimize performance for recursively parsing
header files in Coccinelle.

Coccinelle's C parsing subsystem has an option called --recursive- includes
to recursively parse header files. This is used for type inference/annotation.

Previously, using --recursive-includes on the entire Linux kernel source
code would take far too long. On my computer with the following specs,
- Processor: AMD Ryzen 5 3550H
- RAM: 8 GB
it would take close to 7 hours to complete. The optimization that this
patch series implements reduces that time to 1 hour.

The following is a high-level description of what has been implemented:
- As header files are recursively parsed, they are scanned for the following:
- fields of structs/unions/enums
- typedefs
- function prototypes
- global variables
The names of the above are stored in a "name cache", i.e. a
hashtable to
map the name to the files it is declared in.
- A dependency graph is built to determine dependencies between all the
files in the codebase.
- In the type annotation phase of the C subsystem, if a function call,
struct/union field or identifier is encountered, the type of which
is
not known to the annoter, the name cache is checked for the name.
- The name cache gives a list of files that the name is declared/defined
in. These files are cross checked with the dependency graph to determine if any of these are reachable by the file that the
annoter is
working on.
- If a reachable header file is found, that file is parsed and the type
associated to the name is returned.

Different approaches that were attempted to alleviate this issue, and the
problems with each are as follows:
- Caching the most recently used files: A LRU cache to store ASTs of the
most recently encountered header files. The problem with this
approach
is the amount of memory it takes to cache the header file ASTs.
- Caching the most troublesome files: A pseudo-LFU cache to store files
that cumulatively take the longest to parse, and thus bloat the
time
taken. The problem with this approach is the amount of memory it
takes
to cache the header file ASTs.
- Skipping unparsable locations in header files: Skipping top-level items
in a header file that cannot be parsed. This approach does not
produce
even close to the amount of optimization needed.

The next step from here would be:
- Maintain a small but persistent cache of header files in groups of directories. Leverage multiprocessing for parsing these header
files.
- Leverage multiprocessing to parse header files initially for name extraction.
- Performing some initial matching with the semantic patch to determine if
a C file matches. If matches are found, call the annoter and
recursively
parse header files for type annotation.
- Recursively parse all header files only once and build a large type environment. Use the dependency graph to determine reachability.
This
has potential memory usage issues though.

Changes in v2:
--------------
- Change occurences of 'begin' and 'match' on the same line with something else
to the next line for better readability.

Quoted 8 lines
 Makefile                     |    2 
 parsing_c/includes_cache.ml  |  286
+++++++++++++++++++++++++++++++++++++++++++
 parsing_c/includes_cache.mli |   47 +++++++
 parsing_c/parse_c.ml         |   27 +++-
 parsing_c/type_annoter_c.ml  |  130 ++++++++++++++++---
 5 files changed, 466 insertions(+), 26 deletions(-)

Yikes, the diffstat is the old one. Here's the latest (not very different)

 Makefile                     |    2 
 parsing_c/includes_cache.ml  |  290
+++++++++++++++++++++++++++++++++++++++++++
 parsing_c/includes_cache.mli |   47 ++++++
 parsing_c/parse_c.ml         |   28 +++-
 parsing_c/type_annoter_c.ml  |  134 +++++++++++++++++--
 5 files changed, 475 insertions(+), 26 deletions(-)
Quoted 1 line

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci

Applied
#5 lore raw
In reply to Jaskaran Singh
Quoted 48 lines · Jaskaran Singh

This patch series aims to optimize performance for recursively parsing header files in Coccinelle.

Coccinelle's C parsing subsystem has an option called --recursive-includes to recursively parse header files. This is used for type inference/annotation.

Previously, using --recursive-includes on the entire Linux kernel source code would take far too long. On my computer with the following specs,
- Processor: AMD Ryzen 5 3550H
- RAM: 8 GB
it would take close to 7 hours to complete. The optimization that this patch series implements reduces that time to 1 hour.

The following is a high-level description of what has been implemented:
- As header files are recursively parsed, they are scanned for the following:
- fields of structs/unions/enums
- typedefs
- function prototypes
- global variables
The names of the above are stored in a "name cache", i.e. a hashtable to map the name to the files it is declared in.
- A dependency graph is built to determine dependencies between all the files in the codebase.
- In the type annotation phase of the C subsystem, if a function call, struct/union field or identifier is encountered, the type of which is not known to the annoter, the name cache is checked for the name.
- The name cache gives a list of files that the name is declared/defined in. These files are cross checked with the dependency graph to determine if any of these are reachable by the file that the annoter is working on.
- If a reachable header file is found, that file is parsed and the type associated to the name is returned.

Different approaches that were attempted to alleviate this issue, and the problems with each are as follows:
- Caching the most recently used files: A LRU cache to store ASTs of the most recently encountered header files. The problem with this approach is the amount of memory it takes to cache the header file ASTs.
- Caching the most troublesome files: A pseudo-LFU cache to store files that cumulatively take the longest to parse, and thus bloat the time taken. The problem with this approach is the amount of memory it takes to cache the header file ASTs.
- Skipping unparsable locations in header files: Skipping top-level items in a header file that cannot be parsed. This approach does not produce even close to the amount of optimization needed.

Quoted 11 lines

The next step from here would be:
- Maintain a small but persistent cache of header files in groups of directories. Leverage multiprocessing for parsing these header files.
- Leverage multiprocessing to parse header files initially for name extraction.
- Performing some initial matching with the semantic patch to determine if a C file matches. If matches are found, call the annoter and recursively parse header files for type annotation.
- Recursively parse all header files only once and build a large type environment. Use the dependency graph to determine reachability. This has potential memory usage issues though.

Applied.

Quoted 8 lines

Changes in v2:
--------------
- Change occurences of 'begin' and 'match' on the same line with something else to the next line for better readability.

Quoted 9 lines
 Makefile                     |    2
 parsing_c/includes_cache.ml  |  286 +++++++++++++++++++++++++++++++++++++++++++
 parsing_c/includes_cache.mli |   47 +++++++
 parsing_c/parse_c.ml         |   27 +++-
 parsing_c/type_annoter_c.ml  |  130 ++++++++++++++++---
 5 files changed, 466 insertions(+), 26 deletions(-)

_______________________________________________
Cocci mailing list
[email protected]
https://systeme.lip6.fr/mailman/listinfo/cocci