1# this file contains definitions related to the Linux kernel itself
2#
3
4# list here the macros that you know are always defined/undefined when including
5# the kernel headers
6#
7import sys, cpp, re, os.path, string, time
8from defaults import *
9
10verboseSearch = 0
11verboseFind   = 0
12
13########################################################################
14########################################################################
15#####                                                              #####
16#####           H E A D E R   S C A N N E R                        #####
17#####                                                              #####
18########################################################################
19########################################################################
20
21
22class HeaderScanner:
23    """a class used to non-recursively detect which Linux kernel headers are
24       used by a given set of input source files"""
25
26    # to use the HeaderScanner, do the following:
27    #
28    #    scanner = HeaderScanner()
29    #    for path in <your list of files>:
30    #        scanner.parseFile(path)
31    #
32    #    # get the set of Linux headers included by your files
33    #    headers = scanner.getHeaders()
34    #
35    #    # get the set of of input files that do include Linux headers
36    #    files   = scanner.getFiles()
37    #
38    #    note that the result of getHeaders() is a set of strings, each one
39    #    corresponding to a non-bracketed path name, e.g.:
40    #
41    #        set("linux/types","asm/types.h")
42    #
43
44    # the default algorithm is pretty smart and will analyze the input
45    # files with a custom C pre-processor in order to optimize out macros,
46    # get rid of comments, empty lines, etc..
47    #
48    # this avoids many annoying false positives... !!
49    #
50
51    # this regular expression is used to detect include paths that relate to
52    # the kernel, by default, it selects one of:
53    #    <linux/*>
54    #    <asm/*>
55    #    <asm-generic/*>
56    #    <mtd/*>
57    #
58    re_combined_str=\
59       r"^.*<((%s)/[\d\w_\+\.\-/]*)>.*$" % string.join(kernel_dirs,"|")
60
61    re_combined = re.compile(re_combined_str)
62
63    # some kernel files choose to include files with relative paths (x86 32/64
64    # dispatch for instance)
65    re_rel_dir = re.compile(r'^.*"([\d\w_\+\.\-/]+)".*$')
66
67    def __init__(self,config={}):
68        """initialize a HeaderScanner"""
69        self.reset()
70        self.config = config
71
72    def reset(self,config={}):
73        self.files    = set()  # set of files being parsed for headers
74        self.headers  = {}     # maps headers to set of users
75        self.config   = config
76
77    def checkInclude(self, line, from_file, kernel_root=None):
78        relative = False
79        m = HeaderScanner.re_combined.match(line)
80        if kernel_root and not m:
81            m = HeaderScanner.re_rel_dir.match(line)
82            relative = True
83        if not m: return
84
85        header = m.group(1)
86        if from_file:
87            self.files.add(from_file)
88            if kernel_root and relative:
89                hdr_dir = os.path.realpath(os.path.dirname(from_file))
90                hdr_dir = hdr_dir.replace("%s/" % os.path.realpath(kernel_root),
91                                          "")
92                if hdr_dir:
93                    _prefix = "%s/" % hdr_dir
94                else:
95                    _prefix = ""
96                header = "%s%s" % (_prefix, header)
97
98        if not header in self.headers:
99            self.headers[header] = set()
100
101        if from_file:
102            if verboseFind:
103                print "=== %s uses %s" % (from_file, header)
104            self.headers[header].add(from_file)
105
106    def parseFile(self, path, arch=None, kernel_root=None):
107        """parse a given file for Linux headers"""
108        if not os.path.exists(path):
109            return
110
111        # since tokenizing the file is very slow, we first try a quick grep
112        # to see if this returns any meaningful results. only if this is true
113        # do we do the tokenization"""
114        try:
115            f = open(path, "rt")
116        except:
117            print "!!! can't read '%s'" % path
118            return
119
120        hasIncludes = False
121        for line in f:
122            if (HeaderScanner.re_combined.match(line) or
123                (kernel_root and HeaderScanner.re_rel_dir.match(line))):
124                hasIncludes = True
125                break
126
127        if not hasIncludes:
128            if verboseSearch: print "::: " + path
129            return
130
131        if verboseSearch: print "*** " + path
132
133        list = cpp.BlockParser().parseFile(path)
134        if list:
135            macros = kernel_known_macros.copy()
136            if kernel_root:
137                macros.update(self.config)
138                if arch and arch in kernel_default_arch_macros:
139                    macros.update(kernel_default_arch_macros[arch])
140            list.optimizeMacros(macros)
141            list.optimizeIf01()
142            includes = list.findIncludes()
143            for inc in includes:
144                self.checkInclude(inc, path, kernel_root)
145
146    def getHeaders(self):
147        """return the set of all needed kernel headers"""
148        return set(self.headers.keys())
149
150    def getHeaderUsers(self,header):
151        """return the set of all users for a given header"""
152        return set(self.headers.get(header))
153
154    def getAllUsers(self):
155        """return a dictionary mapping heaaders to their user set"""
156        return self.headers.copy()
157
158    def getFiles(self):
159        """returns the set of files that do include kernel headers"""
160        return self.files.copy()
161
162
163##########################################################################
164##########################################################################
165#####                                                                #####
166#####           H E A D E R   F I N D E R                            #####
167#####                                                                #####
168##########################################################################
169##########################################################################
170
171
172class KernelHeaderFinder:
173    """a class used to scan the kernel headers themselves."""
174
175    # this is different
176    #  from a HeaderScanner because we need to translate the path returned by
177    #  HeaderScanner.getHeaders() into possibly architecture-specific ones.
178    #
179    # for example, <asm/XXXX.h> needs to be translated in <asm-ARCH/XXXX.h>
180    # where ARCH is appropriately chosen
181
182    # here's how to use this:
183    #
184    #    scanner = HeaderScanner()
185    #    for path in <your list of user sources>:
186    #        scanner.parseFile(path)
187    #
188    #    used_headers = scanner.getHeaders()
189    #    finder       = KernelHeaderFinder(used_headers, [ "arm", "x86" ],
190    #                                      "<kernel_include_path>")
191    #    all_headers  = finder.scanForAllArchs()
192    #
193    #   not that the result of scanForAllArchs() is a list of relative
194    #   header paths that are not bracketed
195    #
196
197    def __init__(self,headers,archs,kernel_root,kernel_config):
198        """init a KernelHeaderScanner,
199
200            'headers' is a list or set of headers,
201            'archs' is a list of architectures
202            'kernel_root' is the path to the 'include' directory
203             of your original kernel sources
204        """
205
206        if len(kernel_root) > 0 and kernel_root[-1] != "/":
207            kernel_root += "/"
208        #print "using kernel_root %s" % kernel_root
209        self.archs         = archs
210        self.searched      = set(headers)
211        self.kernel_root   = kernel_root
212        self.kernel_config = kernel_config
213        self.needed        = {}
214        self.setArch(arch=None)
215
216    def setArch(self,arch=None):
217        self.curr_arch = arch
218        self.arch_headers = set()
219        if arch:
220            self.prefix = "asm-%s/" % arch
221        else:
222            self.prefix = None
223
224    def pathFromHeader(self,header):
225        path = header
226        if self.prefix and path.startswith("asm/"):
227            path = "%s%s" % (self.prefix, path[4:])
228        return path
229
230    def pathToHeader(self,path):
231        if self.prefix and path.startswith(self.prefix):
232            path = "asm/%s" % path[len(self.prefix):]
233        return "%s" % path
234
235    def setSearchedHeaders(self,headers):
236        self.searched = set(headers)
237
238    def scanForArch(self):
239        fparser   = HeaderScanner(config=self.kernel_config)
240        workqueue = []
241        needed    = {}
242        for h in self.searched:
243            path = self.pathFromHeader(h)
244            if not path in needed:
245                needed[path] = set()
246            workqueue.append(path)
247
248        i = 0
249        while i < len(workqueue):
250            path = workqueue[i]
251            i   += 1
252            fparser.parseFile(self.kernel_root + path,
253                              arch=self.curr_arch, kernel_root=self.kernel_root)
254            for used in fparser.getHeaders():
255                path  = self.pathFromHeader(used)
256                if not path in needed:
257                    needed[path] = set()
258                    workqueue.append(path)
259                for user in fparser.getHeaderUsers(used):
260                    needed[path].add(user)
261
262        # now copy the arch-specific headers into the global list
263        for header in needed.keys():
264            users = needed[header]
265            if not header in self.needed:
266                self.needed[header] = set()
267
268            for user in users:
269                self.needed[header].add(user)
270
271    def scanForAllArchs(self):
272        """scan for all architectures and return the set of all needed kernel headers"""
273        for arch in self.archs:
274            self.setArch(arch)
275            self.scanForArch()
276
277        return set(self.needed.keys())
278
279    def getHeaderUsers(self,header):
280        """return the set of all users for a given header"""
281        return set(self.needed[header])
282
283    def getArchHeaders(self,arch):
284        """return the set of all <asm/...> headers required by a given architecture"""
285        return set()  # XXX: TODO
286
287#####################################################################################
288#####################################################################################
289#####                                                                           #####
290#####           C O N F I G   P A R S E R                                       #####
291#####                                                                           #####
292#####################################################################################
293#####################################################################################
294
295class ConfigParser:
296    """a class used to parse the Linux kernel .config file"""
297    re_CONFIG_ = re.compile(r"^(CONFIG_\w+)=(.*)$")
298
299    def __init__(self):
300        self.items = {}
301        self.duplicates = False
302
303    def parseLine(self,line):
304        line = string.strip(line)
305
306        # skip empty and comment lines
307        if len(line) == 0 or line[0] == "#":
308            return
309
310        m = ConfigParser.re_CONFIG_.match(line)
311        if not m: return
312
313        name  = m.group(1)
314        value = m.group(2)
315
316        if name in self.items:  # aarg, duplicate value
317            self.duplicates = True
318
319        self.items[name] = value
320
321    def parseFile(self,path):
322        f = file(path, "r")
323        for line in f:
324            if len(line) > 0:
325                if line[-1] == "\n":
326                    line = line[:-1]
327                    if len(line) > 0 and line[-1] == "\r":
328                        line = line[:-1]
329                self.parseLine(line)
330        f.close()
331
332    def getDefinitions(self):
333        """retrieve a dictionary containing definitions for CONFIG_XXX"""
334        return self.items.copy()
335
336    def __repr__(self):
337        return repr(self.items)
338
339    def __str__(self):
340        return str(self.items)
341