| # 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 config.py. See the file README.md.""" |
| |
| 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 = 'https://lore.kernel.org' |
| |
| # User-Agent header to use in requests to the server |
| self.user_agent = 'stable_utils.py/0.1' |
| |
| # 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() |
| try: |
| import config as local_config |
| local_config.customize(config) |
| except ModuleNotFoundError: |
| pass |
| |
| SCRIPT_DIR = Path(__file__).parent |
| LORE_RESULTS_PER_PAGE = 200 |
| 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.now() - |
| 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 = lore_cache.read(req_hash) |
| 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 = requests.post(url, 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(file.name) |
| |
| 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 https://lore.kernel.org/all/_/text/help/""" |
| 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 LORE_RESULTS_SECTION_REGEX.search(pre.text)), 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 = subprocess.run(args, 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): |
| self.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', self.id]) |
| return self._title |
| |
| def get_body(self): |
| """Returns the body of this commit.""" |
| if not self._body: |
| self._body = git(['log', '--pretty=%b', '-1', self.id]) |
| 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 ('/lore.kernel.org/' in link or |
| '/lkml.kernel.org/' 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 BACKPORT_PATCH_SUBJECT_REGEX.search(subject) and |
| not BACKPORT_PATCH_BODY_REGEX.search(str(fetch_message(message_id)))): |
| 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 ('stable@vger.kernel.org' not in msg['To'] and |
| 'stable@vger.kernel.org' 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 {self.id[:12]} ("{self.get_title()}")' |
| |
| def __repr__(self): |
| return self.id |
| |
| 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 = PATCH_NUMBER_REGEX.search(target_subject) |
| if not match: |
| # standalone patch |
| return [None, target_patch] |
| target_patch_idx = int(match.group(1)) |
| num_patches = int(match.group(2)) |
| 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 = PATCH_NUMBER_REGEX.search(subject) |
| if not match: |
| continue |
| i = int(match.group(1)) |
| if i > num_patches or int(match.group(2)) != 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 _extract_kernel_version(commit): |
| major = -1 |
| minor = -1 |
| extraversion = '' |
| for line in git(['show', f'{commit}:Makefile']).split('\n'): |
| if line.startswith('VERSION = '): |
| major = int(line.split()[2]) |
| if line.startswith('PATCHLEVEL = '): |
| minor = int(line.split()[2]) |
| try: |
| if line.startswith('EXTRAVERSION = '): |
| extraversion = line.split()[2] |
| except IndexError: |
| pass |
| if major < 0 or minor < 0: |
| error(f'Failed to extract kernel major.minor version number at {commit}') |
| return (major, minor, extraversion) |
| |
| def extract_kernel_version(commit): |
| """Returns the last v{major}.{minor} tag that the given kernel commit is |
| based on. Release candidates aren't counted, so if for example the commit |
| is based on v6.4-rc1, this returns v6.3.""" |
| (major, minor, extraversion) = _extract_kernel_version(commit) |
| if 'rc' in extraversion: |
| commit = f'v{major}.{minor}-rc1~1' |
| (major, minor, extraversion) = _extract_kernel_version(commit) |
| if extraversion: |
| error(f'Unexpectedly found EXTRAVERSION at {commit}') |
| return f'v{major}.{minor}' |
| |
| 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.""" |
| |
| baseline = extract_kernel_version(end_commit) |
| histfile = f'history_{config.start_of_history}..{baseline}' |
| try: |
| content = git_cache.read(histfile) |
| 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 = subprocess.run(['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 config.py that sets linux_dir.') |
| return args |
