Initial commit

Signed-off-by: Eric Biggers <>
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..473785b
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
diff --git a/COPYING b/COPYING
new file mode 100644
index 0000000..d159169
--- /dev/null
@@ -0,0 +1,339 @@
+                    GNU GENERAL PUBLIC LICENSE
+                       Version 2, June 1991
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+                            Preamble
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users.  This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it.  (Some other Free Software Foundation software is covered by
+the GNU Lesser General Public License instead.)  You can apply it to
+your programs, too.
+  When we speak of free software, we are referring to freedom, not
+price.  Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+  To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+  For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have.  You must make sure that they, too, receive or can get the
+source code.  And you must show them these terms so they know their
+  We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+  Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software.  If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+  Finally, any free program is threatened constantly by software
+patents.  We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary.  To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+  The precise terms and conditions for copying, distribution and
+modification follow.
+                    GNU GENERAL PUBLIC LICENSE
+  0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License.  The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language.  (Hereinafter, translation is included without limitation in
+the term "modification".)  Each licensee is addressed as "you".
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+  1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+  2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+    a) You must cause the modified files to carry prominent notices
+    stating that you changed the files and the date of any change.
+    b) You must cause any work that you distribute or publish, that in
+    whole or in part contains or is derived from the Program or any
+    part thereof, to be licensed as a whole at no charge to all third
+    parties under the terms of this License.
+    c) If the modified program normally reads commands interactively
+    when run, you must cause it, when started running for such
+    interactive use in the most ordinary way, to print or display an
+    announcement including an appropriate copyright notice and a
+    notice that there is no warranty (or else, saying that you provide
+    a warranty) and that users may redistribute the program under
+    these conditions, and telling the user how to view a copy of this
+    License.  (Exception: if the Program itself is interactive but
+    does not normally print such an announcement, your work based on
+    the Program is not required to print an announcement.)
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+  3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+    a) Accompany it with the complete corresponding machine-readable
+    source code, which must be distributed under the terms of Sections
+    1 and 2 above on a medium customarily used for software interchange; or,
+    b) Accompany it with a written offer, valid for at least three
+    years, to give any third party, for a charge no more than your
+    cost of physically performing source distribution, a complete
+    machine-readable copy of the corresponding source code, to be
+    distributed under the terms of Sections 1 and 2 above on a medium
+    customarily used for software interchange; or,
+    c) Accompany it with the information you received as to the offer
+    to distribute corresponding source code.  (This alternative is
+    allowed only for noncommercial distribution and only if you
+    received the program in object code or executable form with such
+    an offer, in accord with Subsection b above.)
+The source code for a work means the preferred form of the work for
+making modifications to it.  For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable.  However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+  4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License.  Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+  5. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Program or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+  6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+  7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+  8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded.  In such case, this License incorporates
+the limitation as if written in the body of this License.
+  9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time.  Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+Each version is given a distinguishing version number.  If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation.  If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+  10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission.  For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this.  Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+                            NO WARRANTY
+                     END OF TERMS AND CONDITIONS
+            How to Apply These Terms to Your New Programs
+  If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+  To do so, attach the following notices to the program.  It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+    <one line to give the program's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    GNU General Public License for more details.
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+Also add information on how to contact you by electronic and paper mail.
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+    Gnomovision version 69, Copyright (C) year name of author
+    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+    This is free software, and you are welcome to redistribute it
+    under certain conditions; type `show c' for details.
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License.  Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary.  Here is a sample; alter the names:
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+  `Gnomovision' (which makes passes at compilers) written by James Hacker.
+  <signature of Ty Coon>, 1 April 1989
+  Ty Coon, President of Vice
+This General Public License does not permit incorporating your program into
+proprietary programs.  If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library.  If this is what you want to do, use the GNU Lesser General
+Public License instead of this License.
diff --git a/ b/
new file mode 100644
index 0000000..1632237
--- /dev/null
+++ b/
@@ -0,0 +1,68 @@
+# Introduction
+This repository contains some scripts that may be helpful for maintenance of
+stable and Long Term Support branches of the Linux kernel.
+# Prerequisites
+Install the following packages:
+- `python`
+- `python-requests`
+- `python-beautifulsoup4`
+# List of scripts
+- `find-orig-patch`: Finds the original patch email from a git commit.
+- `find-orig-series`: Finds the original patch series from a git commit.
+- `find-missing-prereqs`: Finds patches that were backported without previous
+  patches in their original series also being backported.
+For more information, run each script with `--help`.
+If anything goes wrong, using the `--verbose` option might help diagnose it.
+There are also tests, which can be run using ``.
+# Configuration
+Settings such as the location of the Linux git repo are defined by the `Config`
+in ``.  These settings can be overridden by creating a file
+``, in this directory, that contains a method `customize(config)`.  For
+example, your `` could contain:
+import os
+def customize(config):
+    config.linux_dir = os.getenv('HOME') + '/src/linux'
+# Information sources
+These scripts use two sources of information: a local Linux git repo and a
+remote mailing list archive server.
+## Linux git repo
+`config.linux_dir` must be a clone of Linux that contains:
+- Any git commit IDs that are explicitly specified in commands
+- A git ref `config.upstream` (default: `origin/master`) that refers to the
+  latest mainline.  This is used to check whether commits are "upstream".
+- The history going back at least to `config.start_of_history` (default: `v4.0`)
+`config.lore` (default: ``) must be a
+[public-inbox]( server that archives the
+mailing lists that the patches for the git commits are sent to.  The scripts
+query this server to find patches.
+These scripts make a large number of queries, so please don't run these scripts
+excessively.  However, all responses are cached for `config.lore_cache_timeout`
+(default: 24 hours) in the `lore_cache` directory.  So, redundant requests won't
+be made if e.g. a script is run multiple times with the same arguments.
diff --git a/find-missing-prereqs b/find-missing-prereqs
new file mode 100755
index 0000000..e154518
--- /dev/null
+++ b/find-missing-prereqs
@@ -0,0 +1,38 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+import argparse
+from stable_utils import *
+parser = argparse.ArgumentParser(
+        formatter_class=argparse.RawDescriptionHelpFormatter,
+        description=
+"""Finds patches that were backported without previous patches in their original
+series also being backported.  For each series containing such a patch, lists
+the missing previous patches.
+This command requires a commit range.  Normally it should be something like
+stable/linux-6.1.y..HEAD, where HEAD includes the pending patches for 6.1.
+parser.add_argument('--autosel-only', action='store_true',
+                    help="only consider AUTOSEL'd commits")
+args = parse_args(parser)
+for (patches, backports, missing) \
+        in find_missing_prereqs(args.commit_range, args.autosel_only):
+    print('The following commit(s):')
+    for (i, commit) in backports:
+        prefix = ' AUTOSEL' if commit.is_autosel() else ''
+        print(f'  [PATCH{prefix} {i}/{len(patches)-1}] {commit}')
+    print('... are backported without earlier commit(s) in series:')
+    for (i, commit) in missing:
+        print(f'  [PATCH {i}/{len(patches)-1}] {commit}')
+    cover_letter = patches[0]
+    if cover_letter:
+        subject = cover_letter["Subject"].replace('\n', ' ')
+        print(f'Original patch series is "{subject}"')
+        print(f'({config.lore}/r/{get_message_id(cover_letter)})')
+    print('')
diff --git a/find-orig-patch b/find-orig-patch
new file mode 100755
index 0000000..bc01881
--- /dev/null
+++ b/find-orig-patch
@@ -0,0 +1,33 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+import argparse
+from stable_utils import *
+parser = argparse.ArgumentParser(
+        formatter_class=argparse.RawDescriptionHelpFormatter,
+        description=
+"""Finds the original patch email from a git commit.  Uses the message ID from
+the commit message if possible, otherwise falls back to a search of by commit title.""")
+parser.add_argument('--msgid', action='store_true',
+                    help='just output the message ID')
+parser.add_argument('--link', action='store_true',
+                    help='just output a lore link')
+args = parse_args(parser)
+commit = Commit(args.commit_id)
+message_id = commit.find_original_email()
+if not message_id:
+    error(f'Cannot find original patch for {commit}')
+if args.msgid:
+    print(message_id)
+    print(f'{config.lore}/r/{message_id}')
+    raw_message = fetch_raw_message(message_id)
+    sys.stdout.buffer.write(raw_message)
diff --git a/find-orig-series b/find-orig-series
new file mode 100755
index 0000000..b36261d
--- /dev/null
+++ b/find-orig-series
@@ -0,0 +1,29 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+import argparse
+from stable_utils import *
+parser = argparse.ArgumentParser(
+        formatter_class=argparse.RawDescriptionHelpFormatter,
+        description=
+"""Finds the original patch series from a git commit.  Uses the message ID from
+the commit message if possible, otherwise falls back to a search of by commit title.""")
+args = parse_args(parser)
+commit = Commit(args.commit_id)
+message_id = commit.find_original_email()
+if not message_id:
+    error(f'Cannot find original patch for {commit}')
+patches = find_patches_in_same_series(message_id)
+if not patches:
+    error(f'Cannot find original series for {commit}')
+if patches[0]:
+    print(patches[0])
+for patch in patches[1:]:
+    print(patch)
diff --git a/ b/
new file mode 100755
index 0000000..e948e3a
--- /dev/null
+++ b/
@@ -0,0 +1,17 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+set -e -u
+cd "$(dirname "$(realpath "$0")")"
+export PATH="$PWD:$PATH"
+for script in tests/*.py; do
+	echo "Running $script"
+	if ! PYTHONPATH=. python3 "$script"; then
+		echo 1>&2 "$script failed!"
+		exit 1
+	fi
+echo "All tests passed!"
diff --git a/ b/
new file mode 100755
index 0000000..5be0518
--- /dev/null
+++ b/
@@ -0,0 +1,588 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+from pathlib import Path
+import datetime
+import fcntl
+import gzip
+import hashlib
+import mailbox
+import pickle
+import re
+import subprocess
+import sys
+import tempfile
+import urllib.parse
+from bs4 import BeautifulSoup
+import requests
+class Config:
+    """The configuration.  The default values defined below can be overridden by
+    a local file  See the file"""
+    def __init__(self):
+        # Print debug messages?
+        self.verbose = False
+        # Path to the Linux git repo to use
+        self.linux_dir = '.'
+        # First git commit to consider when looking at the history.  Any commits
+        # before this will be ignored to improve performance.
+        self.start_of_history = 'v4.0'
+        # URL of the public-inbox server to query
+        self.lore = ''
+        # User-Agent header to use in requests to the server
+        self.user_agent = ''
+        # Amount of time to locally cache responses from the server before an
+        # identical request will be re-attempted again
+        self.lore_cache_timeout = datetime.timedelta(hours=24)
+        # The git ref name for the latest mainline
+        self.upstream = 'origin/master'
+config = Config()
+    import config as local_config
+    local_config.customize(config)
+except ModuleNotFoundError:
+    pass
+SCRIPT_DIR = Path(__file__).parent
+LORE_RESULTS_SECTION_REGEX = re.compile('- by .* @ [0-9]{4}-[0-9]{2}-[0-9]{2}')
+PATCH_NUMBER_REGEX = re.compile('\\[.*\\s([0-9]+)/([0-9]+).*\\]')
+BACKPORT_PATCH_SUBJECT_REGEX = re.compile('[0-9]+\\.[0-9]+')
+BACKPORT_PATCH_BODY_REGEX = re.compile('(commit [0-9a-f]{40} upstream)|(upstream commit [0-9]{40})',
+                                       re.IGNORECASE)
+WHITESPACE_REGEX = re.compile('\\s+')
+def debug(string):
+    """Prints a DEBUG message if verbose mode is enabled."""
+    if config.verbose:
+        sys.stderr.write(f'[DEBUG] {string}\n')
+def warn(string):
+    """Prints a WARNING message."""
+    sys.stderr.write(f'[WARNING] {string}\n')
+def error(string):
+    """Prints an ERROR message and exits with failure status."""
+    sys.stderr.write(f'[ERROR] {string}\n')
+    sys.exit(1)
+class Cache:
+    """A cache that maps string keys to bytes values, implemented as a
+    directory.  Multi-process safe.  Keys must be valid filenames."""
+    def __init__(self, name, version, timeout):
+        self._dir_path = SCRIPT_DIR / name
+        self._timeout = timeout
+        self._lock_file = SCRIPT_DIR / (name + '.lock')
+        with self._locked():
+            version_file = SCRIPT_DIR / (name + '.version')
+            if self._dir_path.exists():
+                try:
+                    cur_version = int(version_file.read_text())
+                except FileNotFoundError:
+                    cur_version = 0
+                if cur_version != version:
+                    debug(f'Clearing {name}, as it has a different version number')
+                # Delete all expired files.
+                for path in self._dir_path.iterdir():
+                    if cur_version != version or self._is_file_expired(path):
+                        path.unlink()
+                if cur_version != version:
+                    version_file.write_text(f'{version}\n')
+                return
+            self._dir_path.mkdir()
+            version_file.write_text(f'{version}\n')
+    def read(self, key):
+        """Returns the cached value for the given key, or None."""
+        with self._locked():
+            path = self._dir_path / key
+            if self._is_file_expired(path):
+                return None
+            return path.read_bytes()
+    def write(self, key, value):
+        """Writes a key-value pair to this Cache."""
+        with self._locked():
+            path = self._dir_path / key
+            tmp_path = self._dir_path / (key + '.tmp')
+            tmp_path.write_bytes(value)
+            tmp_path.rename(path)
+    def _is_file_expired(self, path):
+        try:
+            age = ( -
+                   datetime.datetime.fromtimestamp(path.stat().st_mtime))
+            return age > self._timeout
+        except FileNotFoundError:
+            return True
+    def _locked(self):
+        return FileLock(self._lock_file)
+class FileLock:
+    """An exclusive file lock, usable with Python's 'with' statement."""
+    def __init__(self, path):
+        self._path = path
+        self._file = None
+    def __enter__(self):
+        self._file = open(self._path, 'wb')
+        fcntl.lockf(self._file, fcntl.LOCK_EX)
+    def __exit__(self, exception_type, exception_value, traceback):
+        fcntl.lockf(self._file, fcntl.LOCK_UN)
+        self._file.close()
+lore_cache = Cache('lore_cache', 1, config.lore_cache_timeout)
+git_cache = Cache('git_cache', 1, datetime.timedelta(days=30))
+def lore_request(url_path, post=False):
+    """Makes a GET or POST request to a public-inbox server, with caching.  On
+    success, returns the resulting content as bytes.  On 404 error, returns
+    None.  On other error, raises an exception."""
+    method = 'POST' if post else 'GET'
+    url = config.lore + '/' + url_path
+    req_hash = hashlib.sha256(f'{method} {url}'.encode('utf-8')).hexdigest()
+    # Return a cached response if possible.
+    content =
+    if content:
+        debug(f'Cache hit for {method} {url}')
+        return content
+    # Cache miss; make the actual request.
+    debug(f'{method} {url}')
+    headers = {'User-Agent': config.user_agent}
+    if post:
+        req =, timeout=30, headers=headers)
+    else:
+        req = requests.get(url, timeout=30, headers=headers)
+    if req.status_code == 404:
+        return None
+    req.raise_for_status()
+    # Decompress the response if needed.
+    content = req.content
+    if content[:3] == b'\x1f\x8B\x08':
+        content = gzip.decompress(content)
+    # Cache and return the response.
+    lore_cache.write(req_hash, content)
+    return content
+def fetch_raw_message(message_id):
+    """Fetches a message from the mailing list archive, given its Message-Id.
+    Returns the message as bytes, or None if the message isn't found."""
+    return lore_request(f'all/{urllib.parse.quote(message_id, safe="")}/raw')
+def fetch_message(message_id):
+    """Fetches a message from the mailing list archive, given its Message-Id.
+    Returns the message as a mailbox.Message object, or None if the message
+    isn't found."""
+    content = fetch_raw_message(message_id)
+    if not content:
+        return None
+    return mailbox.Message(content)
+def fetch_thread(message_id):
+    """Fetches a thread from the mailing list archive, given the Message-Id of
+    any message contained in the thread.  Returns the thread as a mailbox.mbox
+    object, or None if the thread isn't found."""
+    content = lore_request(f'all/{urllib.parse.quote(message_id, safe="")}/t.mbox.gz')
+    if not content:
+        return None
+    with tempfile.NamedTemporaryFile() as file:
+        file.write(content)
+        return mailbox.mbox(
+def list_matching_emails(query_string):
+    """Searches the mailing list archive for email messages that match the given
+    search query string.  The search results are generated as (message_id,
+    subject) tuples in reverse chronological order.  For the supported search
+    query syntax, see"""
+    offset = 0
+    while True:
+        content = lore_request(f'all/?q={urllib.parse.quote(query_string, safe="")}&o={offset}')
+        if not content:
+            break
+        soup = BeautifulSoup(content, 'html.parser')
+        results = next((pre for pre in soup.find_all('pre')
+                        if, None)
+        if not results:
+            break
+        count = 0
+        for a_element in results.find_all('a'):
+            yield (urllib.parse.unquote(a_element['href'].rstrip('/')),
+                   a_element.text)
+            count += 1
+        if count < LORE_RESULTS_PER_PAGE:
+            break
+        offset += count
+# Similar to list_matching_emails(), but downloads the full messages.
+# def fetch_matching_emails(query_string, offset=0):
+    # return lore_request(f'all/?q={urllib.parse.quote(query_string, safe="")}&o={offset}&x=m', post=True)
+def git(args):
+    """Runs a git command on linux_dir and returns its output as a string."""
+    args = ['git'] + args
+    debug('Running command: ' + str(args))
+    try:
+        result =, cwd=config.linux_dir,
+                                check=True, capture_output=True)
+    except subprocess.CalledProcessError as ex:
+        sys.stderr.buffer.write(ex.stderr)
+        error(str(ex))
+    return result.stdout.decode('utf-8', errors='replace').rstrip()
+def normalize_title(string):
+    """Normalizes a commit title or PATCH email subject by normalizing
+    whitespace, stripping bracketed sections, and converting to lower case."""
+    string = string.strip()
+    string = WHITESPACE_REGEX.sub(' ', string)
+    string = string.lower()
+    while string.startswith('['):
+        i = string.find(']')
+        if i == -1:
+            break
+        string = string[i + 1:].strip()
+    return string
+class Commit:
+    """A git commit."""
+    def __init__(self, commit_id):
+ = commit_id
+        self._title = None
+        self._body = None
+    def get_title(self):
+        """Returns the title of this commit."""
+        if not self._title:
+            self._title = git(['log', '--pretty=%s', '-1',])
+        return self._title
+    def get_body(self):
+        """Returns the body of this commit."""
+        if not self._body:
+            self._body = git(['log', '--pretty=%b', '-1',])
+        return self._body
+    def get_message_ids(self):
+        """Returns the list of email Message IDs that are mentioned in this
+        Commit's body via Message-Id and Link tags."""
+        ids = []
+        for line in self.get_body().split('\n'):
+            if line.startswith('Message-Id:'):
+                ids.append(urllib.parse.unquote(line.split()[1].strip('<>')))
+            elif line.startswith('Link:'):
+                link = line.split()[1]
+                if ('/' in link or
+                    '/' in link or
+                    '/patch/msgid/' in link):
+                    ids.append(urllib.parse.unquote(link.strip('/').split('/')[-1]))
+        return ids
+    def find_original_email(self):
+        """Tries to find the original PATCH email for this Commit.  Returns the
+        message ID of the original patch, or None if no original patch is found.
+        This is not 100% reliable, as it relies on heuristics."""
+        normalized_title = normalize_title(self.get_title())
+        # First look for a matching "Message-Id:" or "Link:" in the commit body.
+        for message_id in self.get_message_ids():
+            msg = fetch_message(message_id)
+            if msg and normalized_title == normalize_title(msg['Subject']):
+                return message_id
+        # Fall back to a search by commit title.
+        debug(f'Falling back to search by commit title for {self}')
+        potential_matches = [result for result in self.list_matching_emails()
+                             if normalized_title == normalize_title(result[1])]
+        # Take the first (chronologically last) patch that doesn't look like a
+        # backport -- that is, doesn't contain a number like "5.10" in the
+        # subject line and doesn't contain a line like "commit
+        # 89d77f71f493a3663b10fa812d17f472935d24be upstream" in the body.
+        for (message_id, subject) in potential_matches:
+            if (not and
+                not
+                return message_id
+        # If that still didn't work, then maybe the original patch looked like a
+        # backport.  Take the first (chronologically last) patch that didn't
+        # have stable@ in recipients.
+        for (message_id, subject) in potential_matches:
+            msg = fetch_message(message_id)
+            if ('' not in msg['To'] and
+                '' not in msg['Cc']):
+                return message_id
+        # Nothing worked, oh well...
+        debug(f'Cannot find original email for {self}')
+        return None
+    def list_matching_emails(self):
+        """Lists the emails that have this commit's title in their subject."""
+        return list_matching_emails(f's:"{self.get_title()}"')
+    def is_autosel(self):
+        """Returns true if this commit corresponds to an AUTOSEL patch."""
+        # This is an over-simplistic way to do it, but maybe it's good enough.
+        return any('AUTOSEL' in subject
+                   for (_, subject) in self.list_matching_emails())
+    def __str__(self):
+        return f'commit {[:12]} ("{self.get_title()}")'
+    def __repr__(self):
+        return
+def get_message_id(msg):
+    """Returns the Message-Id of a mailbox.Message object."""
+    return msg['Message-Id'].strip().strip('<>')
+def find_patches_in_same_series(message_id):
+    """Tries to find the patch series containing the patch with the given
+    message ID.  On success, returns the array of patch Messages of length N+1,
+    where N is the number of patches in the series.  Index 0 contains the cover
+    letter, or None if no cover letter was found.  On failure, returns None."""
+    thread = fetch_thread(message_id)
+    if not thread:
+        warn(f'Failed to fetch thread containing {message_id}')
+        return None
+    target_patch = next((msg for msg in thread
+                         if message_id == get_message_id(msg)), None)
+    if not target_patch:
+        warn(f'Thread of {message_id} does not contain itself!')
+        return None
+    target_subject = target_patch['Subject']
+    match =
+    if not match:
+        # standalone patch
+        return [None, target_patch]
+    target_patch_idx = int(
+    num_patches = int(
+    if target_patch_idx > num_patches:
+        warn(f'Invalid patch subject "{target_subject}"')
+        return None
+    patches = [None] * (num_patches + 1)
+    patches[target_patch_idx] = target_patch
+    for msg in thread:
+        subject = msg['Subject'].strip()
+        if not subject.startswith('['):
+            continue
+        match =
+        if not match:
+            continue
+        i = int(
+        if i > num_patches or int( != num_patches:
+            debug(f'Ignoring "{subject}" since it is inconsistent with series containing {message_id}')
+            continue
+        if patches[i]:
+            # Duplicates happen frequently.
+            continue
+        patches[i] = msg
+    if any(not patch for patch in patches[1:]):
+        debug(f'Some patches of series containing {message_id} were not found')
+        return None
+    return patches
+class GitHistoryIndex():
+    """A data structure that maps (normalized) git commit title to the list of
+    commit IDs that have that title."""
+    def __init__(self):
+        self._dict = {}
+    def append(self, start_commit, end_commit):
+        """Appends the history from start_commit to end_commit to this index."""
+        for line in git(['log', '--pretty=%H %s', '--reverse',
+                         f'{start_commit}..{end_commit}']).split('\n'):
+            # Careful: line.split(maxsplit=1) fails on Linux commit
+            # 7b7abfe3dd81d659 which has an empty title!
+            commit_id = bytes.fromhex(line[:40])
+            title = line[41:]
+            self._dict.setdefault(normalize_title(title), []).append(commit_id)
+    def __contains__(self, key):
+        return key in self._dict
+    def get(self, normalized_title):
+        """Returns a list of commit IDs that have the given normalized title."""
+        return self._dict.get(normalized_title, [])
+def get_history_index(end_commit):
+    """Returns a GitHistoryIndex that indexes the history of the Linux kernel by
+    commit title in the range config.start_of_history to end_commit.
+    To speed up repeated executions, the index of the history until the current
+    major.minor version is built on its own and is cached on-disk.  The index of
+    the history until end_commit is then generated by loading the cached index
+    and appending the commits from major.minor to end_commit."""
+    major = -1
+    minor = -1
+    for line in git(['show', f'{end_commit}:Makefile']).split('\n'):
+        if line.startswith('VERSION = '):
+            major = int(line.split()[2])
+        if line.startswith('PATCHLEVEL = '):
+            minor = int(line.split()[2])
+        if major >= 0 and minor >= 0:
+            break
+    if major < 0 or minor < 0:
+        error(f'Failed to extract kernel major.minor version number at {end_commit}')
+    baseline = f'v{major}.{minor}'
+    histfile = f'history_{config.start_of_history}..{baseline}'
+    try:
+        content =
+        if not content:
+            raise FileNotFoundError(f'{histfile} is not cached yet')
+        index = pickle.loads(content)
+        debug(f'Loaded {histfile}')
+    except Exception as ex:
+        debug(str(ex))
+        debug(f'Indexing Linux history {config.start_of_history}..{baseline}')
+        index = GitHistoryIndex()
+        index.append(config.start_of_history, baseline)
+        debug(f'Writing {histfile}')
+        git_cache.write(histfile, pickle.dumps(index))
+    index.append(baseline, end_commit)
+    return index
+def find_missing_prereqs(commit_range, autosel_only=False):
+    """For the given range of backported commits, finds commits that are
+    backported without previous patches in their original series.  Generates a
+    (patches, backports, missing) tuple for each relevant patch series.
+    'patches' is the full original patch series, including the cover letter if
+    availaible, as a list of mailbox.Message objects.  'backports' is a sorted
+    list of tuples of (patch number, backported Commit).  'missing' is a sorted
+    list of tuples of (patch number, missing upstream Commit)."""
+    class Series:
+        def __init__(self, patches):
+            self.patches = patches
+            self.backports = {}
+        def all_message_ids(self):
+            return (get_message_id(patch) for patch in self.patches[1:])
+        def add_backport(self, message_id, commit):
+            for i in range(1, len(self.patches)):
+                if message_id == get_message_id(self.patches[i]):
+                    self.backports[i] = commit
+                    return
+            error(f'{message_id} maps to a series, but patch number not found')
+    def find_original_email_fast(commit, message_id_to_series):
+        """If the commit is explicitly tagged with a message ID that is already
+        present in one of the already-downloaded threads, then assume that is
+        the correct message ID.  This saves some work."""
+        for message_id in commit.get_message_ids():
+            if message_id in message_id_to_series:
+                debug(f'Already found the thread containing {commit}')
+                return message_id
+        return commit.find_original_email()
+    # Expand the given commit range into a list of commit IDs.
+    commit_ids = git(['log', '--reverse', '--pretty=%H', commit_range]).split('\n')
+    # Build an index of the history until the last given commit.
+    downstream_history_index = get_history_index(commit_ids[-1])
+    # Build an index of the history until the latest upstream.
+    upstream_history_index = get_history_index(config.upstream)
+    # All series seen so far
+    all_series = []
+    # Map from message ID to series, for all messages in all series seen so far
+    message_id_to_series = {}
+    # For each specified backport commit...
+    for (i, commit_id) in enumerate(commit_ids):
+        debug(f'Processing commit {i+1} of {len(commit_ids)} [{commit_id}]')
+        commit = Commit(commit_id)
+        # Find the original patch email, then the patch series that contains it.
+        message_id = find_original_email_fast(commit, message_id_to_series)
+        if not message_id:
+            continue
+        series = message_id_to_series.get(message_id)
+        if not series:
+            patches = find_patches_in_same_series(message_id)
+            if not patches:
+                continue
+            # Found a patch series that we haven't seen before.
+            series = Series(patches)
+            all_series.append(series)
+            for mid in series.all_message_ids():
+                message_id_to_series[mid] = series
+        # Keep track of which patches in the series have a backport commit in
+        # the specified range.
+        series.add_backport(message_id, commit)
+    # For each series that was found...
+    for (i, series) in enumerate(all_series):
+        debug(f'Processing series {i+1} of {len(all_series)}')
+        # Get the number of the last patch in the series that is backported.
+        max_backported_patch_num = max(series.backports)
+        missing = {}
+        # Check whether any earlier patches in the series seem to be missing.
+        # (For now, we don't check for *later* missing patches.)
+        for i in range(1, max_backported_patch_num):
+            # Is the patch being backported in the given commit range?
+            if i in series.backports:
+                continue
+            patch = series.patches[i]
+            # Was the patch already backported before the given commit range?
+            title = normalize_title(patch['Subject'])
+            if title in downstream_history_index:
+                continue
+            # Nope, it's probably missing.  Try to find the corresponding
+            # upstream commit.  If it's successfully found, consider it missing.
+            for cid in reversed(upstream_history_index.get(title)):
+                commit = Commit(cid.hex())
+                # Sanity check against find_original_email() before recommending
+                mid = commit.find_original_email()
+                if mid and mid == get_message_id(patch):
+                    missing[i] = commit
+        # If the series has missing patches, report them.
+        if not missing:
+            continue
+        # In --autosel-only mode, suppress reports for series where none of the
+        # backports appear to be from AUTOSEL.
+        if autosel_only and not any(c.is_autosel() for c in series.backports.values()):
+            debug(f'Not reporting missing prerequisites of non-AUTOSEL commits {list(series.backports.values())}')
+            continue
+        yield (series.patches, sorted(series.backports.items()),
+               sorted(missing.items()))
+def parse_args(argparser):
+    """Adds common options and parses the command arguments."""
+    argparser.add_argument('--verbose', action='store_true',
+                           help='show debug messages')
+    args = argparser.parse_args()
+    if args.verbose:
+        config.verbose = True
+    res =['git', 'log', '-1', config.start_of_history],
+                         check=False, capture_output=True, cwd=config.linux_dir)
+    if res.returncode != 0:
+        error('Run this script with the working directory in the kernel repo, or create a that sets linux_dir.')
+    return args
diff --git a/tests/ b/tests/
new file mode 100644
index 0000000..30bbc63
--- /dev/null
+++ b/tests/
@@ -0,0 +1,63 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+from stable_utils import *
+    {
+        'commit_range': '81c1188905f88b77743d1fdeeedfc8cb7b67787d~3..81c1188905f88b77743d1fdeeedfc8cb7b67787d',
+        'results': [
+            {
+                # [PATCH v4 0/5] blk-iocost: random bugfix
+                'cover_letter': '',
+                'backports': [
+                    (4, 'bf8eb1fd6110871e6232e8e7efe399276ef7e6f6'),
+                ],
+                'missing': [
+                    (1, '7b7c5ae4402f810612e84c4ded7a302a61eeba59'),
+                    (2, '235a5a83f637e32646cd004c9b580decf1225566'),
+                    (3, '35198e32300190d52e7f50413dde4f86dea1de92'),
+                ],
+            },
+            {
+                # [PATCH -next v3 0/3] blk-cgroup: make sure pd_free_fn() is called in order
+                'cover_letter': '',
+                'backports': [
+                    (1, '029f1f1efa84387474b445dac4281cf95a398db8'),
+                    (3, '81c1188905f88b77743d1fdeeedfc8cb7b67787d'),
+                ],
+                'missing': [
+                    (2, 'dfd6200a095440b663099d8d42f1efb0175a1ce3'),
+                ],
+            },
+        ],
+    }, {
+        'commit_range': 'a6f81fcb2c3905c28641837dc823ed34617eb110~1..a6f81fcb2c3905c28641837dc823ed34617eb110',
+        'results': [
+            {
+                # [PATCH net-next 0/3] tcp: better receiver autotuning
+                'cover_letter': '',
+                'backports': [
+                    (2, 'a6f81fcb2c3905c28641837dc823ed34617eb110'),
+                ],
+                'missing': [
+                    (1, '02db55718d53f9d426cee504c27fb768e9ed4ffe'),
+                ],
+            },
+        ],
+    },
+def assert_equals(expected, actual):
+    if expected != actual:
+        raise AssertionError(f"Expected '{expected}' but was '{actual}'")
+for case in TEST_CASES:
+    for (i, (patches, backports, missing)) \
+            in enumerate(find_missing_prereqs(case['commit_range'], False)):
+        expected_result = case['results'][i]
+        assert_equals(expected_result['cover_letter'], get_message_id(patches[0]))
+        assert_equals(expected_result['backports'],
+                      [(i, for (i, commit) in backports])
+        assert_equals(expected_result['missing'],
+                      [(i, for (i, commit) in missing])
diff --git a/tests/ b/tests/
new file mode 100644
index 0000000..53e8e17
--- /dev/null
+++ b/tests/
@@ -0,0 +1,75 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# Copyright 2023 Google LLC
+from stable_utils import *
+    # A commit that contains a "Message-Id:" reference to the patch
+    {
+        'commit_title': 'vhost_vdpa: fix unmap process in no-batch mode',
+        'commit_id': 'c82729e06644f4e087f5ff0f91b8fb15e03b8890',
+        'message_id': '',
+        'patch_subject': '[PATCH v3] vhost_vdpa: fix unmap process in no-batch mode',
+    }, {
+        # A commit whose message contains a "Link:" to the patch on
+        'commit_title': 'fsverity: reject FS_IOC_ENABLE_VERITY on mode 3 fds',
+        'commit_id': '04839139213cf60d4c5fc792214a08830e294ff8',
+        'message_id': '',
+        'patch_subject': '[PATCH] fsverity: reject FS_IOC_ENABLE_VERITY on mode 3 fds',
+    }, {
+        # A commit whose message contains a "Link:" to the patch on
+        'commit_title': 'libgcc: add forward declarations for generic library routines',
+        'commit_id': '4f20b7471c57032860065591a17efd3325216bde',
+        'message_id': '',
+        'patch_subject': '[PATCH] libgcc: Add forward declarations for generic library routines',
+    }, {
+        # A commit whose message contains a "Link:" to the patch on a patchwork server
+        'commit_title': 'drm/bridge: tc358767: Set default CLRSIPO count',
+        'commit_id': '01338bb82fed40a6a234c2b36a92367c8671adf0',
+        'message_id': '',
+        'patch_subject': '[PATCH] drm/bridge: tc358767: Set default CLRSIPO count',
+    }, {
+        # A commit whose message doesn't link to the original patch in any way
+        'commit_title': 'block/keyslot-manager: prevent crash when num_slots=1',
+        'commit_id': '47a846536e1bf62626f1c0d8488f3718ce5f8296',
+        'message_id': '',
+        'patch_subject': '[PATCH v2] block/keyslot-manager: prevent crash when num_slots=1',
+    }, {
+        # A commit whose message contains a "Link:" to, but it
+        # goes to a bug report instead of to the patch
+        'commit_title': 'btrfs: set default discard iops_limit to 1000',
+        'commit_id': 'e9f59429b87d35cf23ae9ca19629bd686a1c0304',
+        'message_id': '',
+        'patch_subject': '[PATCH v2 1/2] btrfs: set default discard iops_limit to 1000',
+    }, {
+        # A commit whose message doesn't link to the original patch in any way,
+        # and which was later resent as a backport with an unusually-formatted
+        # subject
+        # (
+        'commit_title': 'tcp: avoid integer overflows in tcp_rcv_space_adjust()',
+        'commit_id': 'a6f81fcb2c3905c28641837dc823ed34617eb110',
+        'message_id': '',
+        'patch_subject': '[PATCH net-next 2/3] tcp: avoid integer overflows in tcp_rcv_space_adjust()',
+    }, {
+        # A commit whose message doesn't link to the original patch in any way,
+        # and which was later resent as a backport without the kernel version
+        # being mentioned in the subject
+        # (
+        'commit_title': 'tcp: do not overshoot window_clamp in tcp_rcv_space_adjust()',
+        'commit_id': '02db55718d53f9d426cee504c27fb768e9ed4ffe',
+        'message_id': '',
+        'patch_subject': '[PATCH net-next 1/3] tcp: do not overshoot window_clamp in tcp_rcv_space_adjust()',
+    },
+def assert_equals(expected, actual):
+    if expected != actual:
+        raise AssertionError(f"Expected '{expected}' but was '{actual}'")
+for case in TEST_CASES:
+    commit = Commit(case['commit_id'])
+    assert_equals(case['commit_title'], commit.get_title())
+    message_id = commit.find_original_email()
+    assert_equals(case['message_id'], message_id)
+    message = fetch_message(message_id)
+    assert_equals(case['patch_subject'], message['Subject'])