moveconfig: A few more features

index 2f674375fd..bacb2d9349 100755
@@ -279,6 +279,24 @@ def get_make_cmd():
         sys.exit('GNU Make not found')
     return ret[0].rstrip()
 
+def get_matched_defconfig(line):
+    """Get the defconfig files that match a pattern
+
+    Args:
+        line: Path or filename to match, e.g. 'configs/snow_defconfig' or
+            'k2*_defconfig'. If no directory is provided, 'configs/' is
+            prepended
+
+    Returns:
+        a list of matching defconfig files
+    """
+    dirname = os.path.dirname(line)
+    if dirname:
+        pattern = line
+    else:
+        pattern = os.path.join('configs', line)
+    return glob.glob(pattern) + glob.glob(pattern + '_defconfig')
+
 def get_matched_defconfigs(defconfigs_file):
     """Get all the defconfig files that match the patterns in a file."""
     defconfigs = []

@@ -286,12 +304,10 @@ def get_matched_defconfigs(defconfigs_file):
         line = line.strip()
         if not line:
             continue # skip blank lines silently
-        pattern = os.path.join('configs', line)
-        matched = glob.glob(pattern) + glob.glob(pattern + '_defconfig')
+        matched = get_matched_defconfig(line)
         if not matched:
-            print >> sys.stderr, "warning: %s:%d: no defconfig matched '%s'" % \
-                                                 (defconfigs_file, i + 1, line)
-
+            print >> sys.stderr, ("warning: %s:%d: no defconfig matched '%s'" %
+                                  (defconfigs_file, i + 1, line))
         defconfigs += matched
 
     # use set() to drop multiple matching

index bacb2d9349..7a302d9404 100755
@@ -298,9 +298,22 @@ def get_matched_defconfig(line):
     return glob.glob(pattern) + glob.glob(pattern + '_defconfig')
 
 def get_matched_defconfigs(defconfigs_file):
-    """Get all the defconfig files that match the patterns in a file."""
+    """Get all the defconfig files that match the patterns in a file.
+
+    Args:
+        defconfigs_file: File containing a list of defconfigs to process, or
+            '-' to read the list from stdin
+
+    Returns:
+        A list of paths to defconfig files, with no duplicates
+    """
     defconfigs = []
-    for i, line in enumerate(open(defconfigs_file)):
+    if defconfigs_file == '-':
+        fd = sys.stdin
+        defconfigs_file = 'stdin'
+    else:
+        fd = open(defconfigs_file)
+    for i, line in enumerate(fd):
         line = line.strip()
         if not line:
             continue # skip blank lines silently

@@ -1329,7 +1342,9 @@ def main():
     parser.add_option('-C', '--commit', action='store_true', default=False,
                       help='Create a git commit for the operation')
     parser.add_option('-d', '--defconfigs', type='string',
-                      help='a file containing a list of defconfigs to move')
+                      help='a file containing a list of defconfigs to move, '
+                      "one per line (for example 'snow_defconfig') "
+                      "or '-' to read from stdin")
     parser.add_option('-n', '--dry-run', action='store_true', default=False,
                       help='perform a trial run (show log with no changes)')
     parser.add_option('-e', '--exit-on-error', action='store_true',

index 7a302d9404..059abb8858 100755
@@ -115,6 +115,19 @@ use your own.  Instead of modifying the list directly, you can give
 them via environments.
 
 
+Tips and trips
+--------------
+
+To sync only X86 defconfigs:
+
+   grep -l X86 configs/* | ./tools/moveconfig.py -s -d -
+
+To process CONFIG_CMD_FPGAD only for a subset of configs based on path match:
+
+   ls configs/{hrcon*,iocon*,strider*} | \
+       ./tools/moveconfig.py -Cy CONFIG_CMD_FPGAD -d -
+
+
 Available options
 -----------------
 

@@ -128,7 +141,7 @@ Available options
 
  -d, --defconfigs
   Specify a file containing a list of defconfigs to move.  The defconfig
-  files can be given with shell-style wildcards.
+  files can be given with shell-style wildcards. Use '-' to read from stdin.
 
  -n, --dry-run
    Perform a trial run that does not make any changes.  It is useful to

@@ -169,7 +182,8 @@ Available options
 
  -y, --yes
    Instead of prompting, automatically go ahead with all operations. This
-   includes cleaning up headers and CONFIG_SYS_EXTRA_OPTIONS.
+   includes cleaning up header, CONFIG_SYS_EXTRA_OPTIONS, the config whitelist
+   and the README.
 
 To see the complete list of supported options, run
 

index 059abb8858..ba40c33521 100755
@@ -259,6 +259,9 @@ COLOR_LIGHT_PURPLE = '1;35'
 COLOR_LIGHT_CYAN   = '1;36'
 COLOR_WHITE        = '1;37'
 
+AUTO_CONF_PATH = 'include/config/auto.conf'
+
+
 ### helper functions ###
 def get_devnull():
     """Get the file object of '/dev/null' device."""

@@ -748,8 +751,7 @@ class KconfigParser:
         self.autoconf = os.path.join(build_dir, 'include', 'autoconf.mk')
         self.spl_autoconf = os.path.join(build_dir, 'spl', 'include',
                                          'autoconf.mk')
-        self.config_autoconf = os.path.join(build_dir, 'include', 'config',
-                                            'auto.conf')
+        self.config_autoconf = os.path.join(build_dir, AUTO_CONF_PATH)
         self.defconfig = os.path.join(build_dir, 'defconfig')
 
     def get_cross_compile(self):

@@ -1067,7 +1069,7 @@ class Slot:
         self.state = STATE_DEFCONFIG
 
     def do_autoconf(self):
-        """Run 'make include/config/auto.conf'."""
+        """Run 'make AUTO_CONF_PATH'."""
 
         self.cross_compile = self.parser.get_cross_compile()
         if self.cross_compile is None:

@@ -1080,7 +1082,7 @@ class Slot:
         if self.cross_compile:
             cmd.append('CROSS_COMPILE=%s' % self.cross_compile)
         cmd.append('KCONFIG_IGNORE_DUPLICATES=1')
-        cmd.append('include/config/auto.conf')
+        cmd.append(AUTO_CONF_PATH)
         self.ps = subprocess.Popen(cmd, stdout=self.devnull,
                                    stderr=subprocess.PIPE,
                                    cwd=self.current_src_dir)

index ba40c33521..ed576f4b83 100755
@@ -199,11 +199,13 @@ import glob
 import multiprocessing
 import optparse
 import os
+import Queue
 import re
 import shutil
 import subprocess
 import sys
 import tempfile
+import threading
 import time
 
 SHOW_GNU_MAKE = 'scripts/show-gnu-make'

@@ -260,6 +262,7 @@ COLOR_LIGHT_CYAN   = '1;36'
 COLOR_WHITE        = '1;37'
 
 AUTO_CONF_PATH = 'include/config/auto.conf'
+CONFIG_DATABASE = 'moveconfig.db'
 
 
 ### helper functions ###

@@ -937,6 +940,34 @@ class KconfigParser:
 
         return log
 
+
+class DatabaseThread(threading.Thread):
+    """This thread processes results from Slot threads.
+
+    It collects the data in the master config directary. There is only one
+    result thread, and this helps to serialise the build output.
+    """
+    def __init__(self, config_db, db_queue):
+        """Set up a new result thread
+
+        Args:
+            builder: Builder which will be sent each result
+        """
+        threading.Thread.__init__(self)
+        self.config_db = config_db
+        self.db_queue= db_queue
+
+    def run(self):
+        """Called to start up the result thread.
+
+        We collect the next result job and pass it on to the build.
+        """
+        while True:
+            defconfig, configs = self.db_queue.get()
+            self.config_db[defconfig] = configs
+            self.db_queue.task_done()
+
+
 class Slot:
 
     """A slot to store a subprocess.

@@ -946,7 +977,8 @@ class Slot:
     for faster processing.
     """
 
-    def __init__(self, configs, options, progress, devnull, make_cmd, reference_src_dir):
+    def __init__(self, configs, options, progress, devnull, make_cmd,
+                 reference_src_dir, db_queue):
         """Create a new process slot.
 
         Arguments:

@@ -957,6 +989,7 @@ class Slot:
           make_cmd: command name of GNU Make.
           reference_src_dir: Determine the true starting config state from this
                              source tree.
+          db_queue: output queue to write config info for the database
         """
         self.options = options
         self.progress = progress

@@ -964,6 +997,7 @@ class Slot:
         self.devnull = devnull
         self.make_cmd = (make_cmd, 'O=' + self.build_dir)
         self.reference_src_dir = reference_src_dir
+        self.db_queue = db_queue
         self.parser = KconfigParser(configs, options, self.build_dir)
         self.state = STATE_IDLE
         self.failed_boards = set()

@@ -1039,6 +1073,8 @@ class Slot:
             if self.current_src_dir:
                 self.current_src_dir = None
                 self.do_defconfig()
+            elif self.options.build_db:
+                self.do_build_db()
             else:
                 self.do_savedefconfig()
         elif self.state == STATE_SAVEDEFCONFIG:

@@ -1088,6 +1124,17 @@ class Slot:
                                    cwd=self.current_src_dir)
         self.state = STATE_AUTOCONF
 
+    def do_build_db(self):
+        """Add the board to the database"""
+        configs = {}
+        with open(os.path.join(self.build_dir, AUTO_CONF_PATH)) as fd:
+            for line in fd.readlines():
+                if line.startswith('CONFIG'):
+                    config, value = line.split('=', 1)
+                    configs[config] = value.rstrip()
+        self.db_queue.put([self.defconfig, configs])
+        self.finish(True)
+
     def do_savedefconfig(self):
         """Update the .config and run 'make savedefconfig'."""
 

@@ -1170,7 +1217,7 @@ class Slots:
 
     """Controller of the array of subprocess slots."""
 
-    def __init__(self, configs, options, progress, reference_src_dir):
+    def __init__(self, configs, options, progress, reference_src_dir, db_queue):
         """Create a new slots controller.
 
         Arguments:

@@ -1179,6 +1226,7 @@ class Slots:
           progress: A progress indicator.
           reference_src_dir: Determine the true starting config state from this
                              source tree.
+          db_queue: output queue to write config info for the database
         """
         self.options = options
         self.slots = []

@@ -1186,7 +1234,7 @@ class Slots:
         make_cmd = get_make_cmd()
         for i in range(options.jobs):
             self.slots.append(Slot(configs, options, progress, devnull,
-                                   make_cmd, reference_src_dir))
+                                   make_cmd, reference_src_dir, db_queue))
 
     def add(self, defconfig):
         """Add a new subprocess if a vacant slot is found.

@@ -1298,7 +1346,7 @@ class ReferenceSource:
 
         return self.src_dir
 
-def move_config(configs, options):
+def move_config(configs, options, db_queue):
     """Move config options to defconfig files.
 
     Arguments:

@@ -1308,6 +1356,8 @@ def move_config(configs, options):
     if len(configs) == 0:
         if options.force_sync:
             print 'No CONFIG is specified. You are probably syncing defconfigs.',
+        elif options.build_db:
+            print 'Building %s database' % CONFIG_DATABASE
         else:
             print 'Neither CONFIG nor --force-sync is specified. Nothing will happen.',
     else:

@@ -1326,7 +1376,7 @@ def move_config(configs, options):
         defconfigs = get_all_defconfigs()
 
     progress = Progress(len(defconfigs))
-    slots = Slots(configs, options, progress, reference_src_dir)
+    slots = Slots(configs, options, progress, reference_src_dir, db_queue)
 
     # Main loop to process defconfig files:
     #  Add a new subprocess into a vacant slot.

@@ -1353,6 +1403,8 @@ def main():
 
     parser = optparse.OptionParser()
     # Add options here
+    parser.add_option('-b', '--build-db', action='store_true', default=False,
+                      help='build a CONFIG database')
     parser.add_option('-c', '--color', action='store_true', default=False,
                       help='display the log in color')
     parser.add_option('-C', '--commit', action='store_true', default=False,

@@ -1385,7 +1437,7 @@ def main():
 
     (options, configs) = parser.parse_args()
 
-    if len(configs) == 0 and not options.force_sync:
+    if len(configs) == 0 and not any((options.force_sync, options.build_db)):
         parser.print_usage()
         sys.exit(1)
 

@@ -1395,10 +1447,17 @@ def main():
 
     check_top_directory()
 
+    config_db = {}
+    db_queue = Queue.Queue()
+    t = DatabaseThread(config_db, db_queue)
+    t.setDaemon(True)
+    t.start()
+
     if not options.cleanup_headers_only:
         check_clean_directory()
         update_cross_compile(options.color)
-        move_config(configs, options)
+        move_config(configs, options, db_queue)
+        db_queue.join()
 
     if configs:
         cleanup_headers(configs, options)

@@ -1418,5 +1477,13 @@ def main():
             msg += '\n\nRsync all defconfig files using moveconfig.py'
         subprocess.call(['git', 'commit', '-s', '-m', msg])
 
+    if options.build_db:
+        with open(CONFIG_DATABASE, 'w') as fd:
+            for defconfig, configs in config_db.iteritems():
+                print >>fd, '%s' % defconfig
+                for config in sorted(configs.keys()):
+                    print >>fd, '   %s=%s' % (config, configs[config])
+                print >>fd
+
 if __name__ == '__main__':
     main()

index ba40c33521..ed576f4b83 100755
@@ -199,11 +199,13 @@ import glob
 import multiprocessing
 import optparse
 import os
+import Queue
 import re
 import shutil
 import subprocess
 import sys
 import tempfile
+import threading
 import time
 
 SHOW_GNU_MAKE = 'scripts/show-gnu-make'

@@ -260,6 +262,7 @@ COLOR_LIGHT_CYAN   = '1;36'
 COLOR_WHITE        = '1;37'
 
 AUTO_CONF_PATH = 'include/config/auto.conf'
+CONFIG_DATABASE = 'moveconfig.db'
 
 
 ### helper functions ###

@@ -937,6 +940,34 @@ class KconfigParser:
 
         return log
 
+
+class DatabaseThread(threading.Thread):
+    """This thread processes results from Slot threads.
+
+    It collects the data in the master config directary. There is only one
+    result thread, and this helps to serialise the build output.
+    """
+    def __init__(self, config_db, db_queue):
+        """Set up a new result thread
+
+        Args:
+            builder: Builder which will be sent each result
+        """
+        threading.Thread.__init__(self)
+        self.config_db = config_db
+        self.db_queue= db_queue
+
+    def run(self):
+        """Called to start up the result thread.
+
+        We collect the next result job and pass it on to the build.
+        """
+        while True:
+            defconfig, configs = self.db_queue.get()
+            self.config_db[defconfig] = configs
+            self.db_queue.task_done()
+
+
 class Slot:
 
     """A slot to store a subprocess.

@@ -946,7 +977,8 @@ class Slot:
     for faster processing.
     """
 
-    def __init__(self, configs, options, progress, devnull, make_cmd,

index ed576f4b83..f33203d51b 100755
@@ -128,6 +128,69 @@ To process CONFIG_CMD_FPGAD only for a subset of configs based on path match:
        ./tools/moveconfig.py -Cy CONFIG_CMD_FPGAD -d -
 
 
+Finding implied CONFIGs
+-----------------------
+
+Some CONFIG options can be implied by others and this can help to reduce
+the size of the defconfig files. For example, CONFIG_X86 implies
+CONFIG_CMD_IRQ, so we can put 'imply CMD_IRQ' under 'config X86' and
+all x86 boards will have that option, avoiding adding CONFIG_CMD_IRQ to
+each of the x86 defconfig files.
+
+This tool can help find such configs. To use it, first build a database:
+
+    ./tools/moveconfig.py -b
+
+Then try to query it:
+
+    ./tools/moveconfig.py -i CONFIG_CMD_IRQ
+    CONFIG_CMD_IRQ found in 311/2384 defconfigs
+    44 : CONFIG_SYS_FSL_ERRATUM_IFC_A002769
+    41 : CONFIG_SYS_FSL_ERRATUM_A007075
+    31 : CONFIG_SYS_FSL_DDR_VER_44
+    28 : CONFIG_ARCH_P1010
+    28 : CONFIG_SYS_FSL_ERRATUM_P1010_A003549
+    28 : CONFIG_SYS_FSL_ERRATUM_SEC_A003571
+    28 : CONFIG_SYS_FSL_ERRATUM_IFC_A003399
+    25 : CONFIG_SYS_FSL_ERRATUM_A008044
+    22 : CONFIG_ARCH_P1020
+    21 : CONFIG_SYS_FSL_DDR_VER_46
+    20 : CONFIG_MAX_PIRQ_LINKS
+    20 : CONFIG_HPET_ADDRESS
+    20 : CONFIG_X86
+    20 : CONFIG_PCIE_ECAM_SIZE
+    20 : CONFIG_IRQ_SLOT_COUNT
+    20 : CONFIG_I8259_PIC
+    20 : CONFIG_CPU_ADDR_BITS
+    20 : CONFIG_RAMBASE
+    20 : CONFIG_SYS_FSL_ERRATUM_A005871
+    20 : CONFIG_PCIE_ECAM_BASE
+    20 : CONFIG_X86_TSC_TIMER
+    20 : CONFIG_I8254_TIMER
+    20 : CONFIG_CMD_GETTIME
+    19 : CONFIG_SYS_FSL_ERRATUM_A005812
+    18 : CONFIG_X86_RUN_32BIT
+    17 : CONFIG_CMD_CHIP_CONFIG
+    ...
+
+This shows a list of config options which might imply CONFIG_CMD_EEPROM along
+with how many defconfigs they cover. From this you can see that CONFIG_X86
+implies CONFIG_CMD_EEPROM. Therefore, instead of adding CONFIG_CMD_EEPROM to
+the defconfig of every x86 board, you could add a single imply line to the
+Kconfig file:
+
+    config X86
+        bool "x86 architecture"
+        ...
+        imply CMD_EEPROM
+
+That will cover 20 defconfigs. Many of the options listed are not suitable as
+they are not related. E.g. it would be odd for CONFIG_CMD_GETTIME to imply
+CMD_EEPROM.
+
+Using this search you can reduce the size of moveconfig patches.
+
+
 Available options
 -----------------
 

@@ -191,6 +254,7 @@ To see the complete list of supported options, run
 
 """
 
+import collections
 import copy
 import difflib
 import filecmp

@@ -1395,6 +1459,148 @@ def move_config(configs, options, db_queue):
     slots.show_failed_boards()
     slots.show_suspicious_boards()
 
+def imply_config(config_list, find_superset=False):
+    """Find CONFIG options which imply those in the list
+
+    Some CONFIG options can be implied by others and this can help to reduce
+    the size of the defconfig files. For example, CONFIG_X86 implies
+    CONFIG_CMD_IRQ, so we can put 'imply CMD_IRQ' under 'config X86' and
+    all x86 boards will have that option, avoiding adding CONFIG_CMD_IRQ to
+    each of the x86 defconfig files.
+
+    This function uses the moveconfig database to find such options. It
+    displays a list of things that could possibly imply those in the list.
+    The algorithm ignores any that start with CONFIG_TARGET since these
+    typically refer to only a few defconfigs (often one). It also does not
+    display a config with less than 5 defconfigs.
+
+    The algorithm works using sets. For each target config in config_list:
+        - Get the set 'defconfigs' which use that target config
+        - For each config (from a list of all configs):
+            - Get the set 'imply_defconfig' of defconfigs which use that config
+            -
+            - If imply_defconfigs contains anything not in defconfigs then
+              this config does not imply the target config
+
+    Params:
+        config_list: List of CONFIG options to check (each a string)
+        find_superset: True to look for configs which are a superset of those
+            already found. So for example if CONFIG_EXYNOS5 implies an option,
+            but CONFIG_EXYNOS covers a larger set of defconfigs and also
+            implies that option, this will drop the former in favour of the
+            latter. In practice this option has not proved very used.
+
+    Note the terminoloy:
+        config - a CONFIG_XXX options (a string, e.g. 'CONFIG_CMD_EEPROM')
+        defconfig - a defconfig file (a string, e.g. 'configs/snow_defconfig')
+    """
+    # key is defconfig name, value is dict of (CONFIG_xxx, value)
+    config_db = {}
+
+    # Holds a dict containing the set of defconfigs that contain each config
+    # key is config, value is set of defconfigs using that config
+    defconfig_db = collections.defaultdict(set)
+
+    # Set of all config options we have seen
+    all_configs = set()
+
+    # Set of all defconfigs we have seen
+    all_defconfigs = set()
+
+    # Read in the database
+    configs = {}
+    with open(CONFIG_DATABASE) as fd:
+        for line in fd.readlines():
+            line = line.rstrip()
+            if not line:  # Separator between defconfigs
+                config_db[defconfig] = configs
+                all_defconfigs.add(defconfig)
+                configs = {}
+            elif line[0] == ' ':  # CONFIG line
+                config, value = line.strip().split('=', 1)
+                configs[config] = value
+                defconfig_db[config].add(defconfig)
+                all_configs.add(config)
+            else:  # New defconfig
+                defconfig = line
+
+    # Work through each target config option in tern, independently
+    for config in config_list:
+        defconfigs = defconfig_db.get(config)
+        if not defconfigs:
+            print '%s not found in any defconfig' % config
+            continue
+
+        # Get the set of defconfigs without this one (since a config cannot
+        # imply itself)
+        non_defconfigs = all_defconfigs - defconfigs
+        num_defconfigs = len(defconfigs)
+        print '%s found in %d/%d defconfigs' % (config, num_defconfigs,
+                                                len(all_configs))
+
+        # This will hold the results: key=config, value=defconfigs containing it
+        imply_configs = {}
+        rest_configs = all_configs - set([config])
+
+        # Look at every possible config, except the target one
+        for imply_config in rest_configs:
+            if 'CONFIG_TARGET' in imply_config:
+                continue
+
+            # Find set of defconfigs that have this config
+            imply_defconfig = defconfig_db[imply_config]
+
+            # Get the intersection of this with defconfigs containing the
+            # target config
+            common_defconfigs = imply_defconfig & defconfigs
+
+            # Get the set of defconfigs containing this config which DO NOT
+            # also contain the taret config. If this set is non-empty it means
+            # that this config affects other defconfigs as well as (possibly)
+            # the ones affected by the target config. This means it implies
+            # things we don't want to imply.
+            not_common_defconfigs = imply_defconfig & non_defconfigs
+            if not_common_defconfigs:
+                continue
+
+            # If there are common defconfigs, imply_config may be useful
+            if common_defconfigs:
+                skip = False
+                if find_superset:
+                    for prev in imply_configs.keys():
+                        prev_count = len(imply_configs[prev])
+                        count = len(common_defconfigs)
+                        if (prev_count > count and
+                            (imply_configs[prev] & common_defconfigs ==
+                            common_defconfigs)):
+                            # skip imply_config because prev is a superset
+                            skip = True
+                            break
+                        elif count > prev_count:
+                            # delete prev because imply_config is a superset
+                            del imply_configs[prev]
+                if not skip:
+                    imply_configs[imply_config] = common_defconfigs
+
+        # Now we have a dict imply_configs of configs which imply each config
+        # The value of each dict item is the set of defconfigs containing that
+        # config. Rank them so that we print the configs that imply the largest
+        # number of defconfigs first.
+        ranked_configs = sorted(imply_configs,
+                            key=lambda k: len(imply_configs[k]), reverse=True)
+        for config in ranked_configs:
+            num_common = len(imply_configs[config])
+
+            # Don't bother if there are less than 5 defconfigs affected.
+            if num_common < 5:
+                continue
+            missing = defconfigs - imply_configs[config]
+            missing_str = ', '.join(missing) if missing else 'all'
+            missing_str = ''
+            print '    %d : %-30s%s' % (num_common, config.ljust(30),
+                                        missing_str)
+
+
 def main():
     try:
         cpu_count = multiprocessing.cpu_count()

@@ -1413,6 +1619,8 @@ def main():
                       help='a file containing a list of defconfigs to move, '
                       "one per line (for example 'snow_defconfig') "
                       "or '-' to read from stdin")
+    parser.add_option('-i', '--imply', action='store_true', default=False,
+                      help='find options which imply others')
     parser.add_option('-n', '--dry-run', action='store_true', default=False,
                       help='perform a trial run (show log with no changes)')
     parser.add_option('-e', '--exit-on-error', action='store_true',

@@ -1437,7 +1645,8 @@ def main():
 
     (options, configs) = parser.parse_args()
 
-    if len(configs) == 0 and not any((options.force_sync, options.build_db)):
+    if len(configs) == 0 and not any((options.force_sync, options.build_db,
+                                      options.imply)):
         parser.print_usage()
         sys.exit(1)
 

@@ -1447,6 +1656,10 @@ def main():
 
     check_top_directory()
 
+    if options.imply:
+        imply_config(configs)
+        return
+
     config_db = {}
     db_queue = Queue.Queue()
     t = DatabaseThread(config_db, db_queue)