From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 09202C02183 for ; Tue, 14 Jan 2025 11:02:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 929C36B0085; Tue, 14 Jan 2025 06:02:48 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 8D9736B0088; Tue, 14 Jan 2025 06:02:48 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7A16B6B0089; Tue, 14 Jan 2025 06:02:48 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 5C06A6B0085 for ; Tue, 14 Jan 2025 06:02:48 -0500 (EST) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id CE806140897 for ; Tue, 14 Jan 2025 11:02:47 +0000 (UTC) X-FDA: 83005769574.26.78C8A0C Received: from mail-lf1-f52.google.com (mail-lf1-f52.google.com [209.85.167.52]) by imf03.hostedemail.com (Postfix) with ESMTP id E560F20012 for ; Tue, 14 Jan 2025 11:02:45 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=HqNEYddA; spf=pass (imf03.hostedemail.com: domain of dvyukov@google.com designates 209.85.167.52 as permitted sender) smtp.mailfrom=dvyukov@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1736852566; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=tkDcNJulp0KAE0ecW8Wxpxi/6ej7l7BU9iILAcZFrUc=; b=cT9rm7ac7/E+FJqPimz+WcmgKcC7lLUM/tBIiHFItTdS2hCKzDOc3GEp6h5LBuhqIN6dcB 9alHIBgPridWizYfO0TXyDqU+Q+ZvX2pYagUdkLWkKa3nKaY4gYEOUeLGAsFkuowdw44be PtFcuUcl1qOIChZJEnZmiDS2ihGy/k4= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=HqNEYddA; spf=pass (imf03.hostedemail.com: domain of dvyukov@google.com designates 209.85.167.52 as permitted sender) smtp.mailfrom=dvyukov@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1736852566; a=rsa-sha256; cv=none; b=vn3ZdOKBTqTJN5Z6xRrW3frvLuYuMIGqz39v8MHugwPg5grM/CRMBudI7IB6u7ZkCs1Vlr X5ModReUGKucvmF8GsYtoUWK2k6z2mAJRN4bG0uKevYwEf+gBKHf7cFyRdf4Lt4hn/i7ye 59UySMCsJVssdYXPkaugPV4H8bV+3oI= Received: by mail-lf1-f52.google.com with SMTP id 2adb3069b0e04-54252789365so6216144e87.0 for ; Tue, 14 Jan 2025 03:02:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1736852564; x=1737457364; darn=kvack.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=tkDcNJulp0KAE0ecW8Wxpxi/6ej7l7BU9iILAcZFrUc=; b=HqNEYddAKv339K5WxvrFpld0RNUoO0MTkpQGuQXcR3Lz1f6zsxrLtjVW0irU4x+byd 2K2d8L3YVowMuMtASBw7hMCj6eTdflEPNlcmTaQjqjEa+Y0e9O0ztnbLUHLFr4fGzgxR WVoEys8mdqQvNqU2eUA/zOeb4Y0gCUjfuwWsa+6j39zz6zpv2HvmWgfpEMHKWWy169ML 4ejcTtJuNsd4R+T9/ILlteu51qTMt61hGXgJLlNyFPUSov5yf/pmBLvVXvaAgs31dnvy xMXeWyhaCZrsCAswY7zdQo6z9xQZg/6SDo3IYsf0EGmBdavtqNI8eZrk9u9ezhxvQwee Xb7Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736852564; x=1737457364; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=tkDcNJulp0KAE0ecW8Wxpxi/6ej7l7BU9iILAcZFrUc=; b=HcplXU1Ffdb/KUUeqUualqNISXlGiEUeoehA1yRoYOIqM41hp/XmetqLf6Jdqozps+ 2+SYbgIQIikyAtE1Nta3nOTVElckX7rc56zf3vXaquG4k8RX42nuUckbvUKBaCccpJ9V fBU+xshKaWR/RsgOqt3oMEVKr4aPwGsWIOygG8TFP2MZi21LA3pmQBkANnYXPnuOZLcI E50Wrf5Kz7XGazCypwUMoKnrzTtLIi/Lz8Y4M2ITnCPZ3wCT6OeoJER3vjeZWy/pg9lo PZEEDDPYQJgPHEyx/WLJniuiKL4YezgjBsvRw9q/YLc0TL2Ia192EEUVCYVidd2BQjc/ GRkA== X-Forwarded-Encrypted: i=1; AJvYcCUPylyWGrZKBf/M97bbIBoyt+agP5VCYGugYf3NeKWzadLIVX+klwlya4Wq+qgr28G3SF9mbq5+yg==@kvack.org X-Gm-Message-State: AOJu0YxBVJxSo0hR/V5zGyuYE3tqeYyprZalv4O+LXNVIcF8TMkwfTNi a7e3lZV6vfrpMqpMzjcAVKzx4aQ2sMUqGVXOwoKAA/XFQWzJodGj9/yezceS29xZYAJIQuYm8ut hTyF0kmWa9tBrqGAblIye5iOzjTgElZBzPhd9 X-Gm-Gg: ASbGncv/CT7LqsRtB6cjtvBtbF6js/JCTETLo86i/P252syz0ue1mtpm4UjNhaH3VYG hofPGvju59CyBfE3FIU8QmoBlY05PpKXtpgcMcXEjPWe6jWoAH7zlDrNqRUzr0lkl3HC3 X-Google-Smtp-Source: AGHT+IFf7P01M57Y+Gqy83yzIJ8jPqDjZgPJXvExL+TT5lSQl/qu1v6b8b1aedUzQTWqMr/JTwypkmUtqg6Oh/W0giE= X-Received: by 2002:a05:6512:238e:b0:542:97b9:89e8 with SMTP id 2adb3069b0e04-54297b98aa9mr3302952e87.23.1736852563653; Tue, 14 Jan 2025 03:02:43 -0800 (PST) MIME-Version: 1.0 References: <20250114-kcov-v1-0-004294b931a2@quicinc.com> In-Reply-To: From: Dmitry Vyukov Date: Tue, 14 Jan 2025 12:02:31 +0100 X-Gm-Features: AbW1kvbVjib7z1JcHA7nqt52tIMjbajYXxACvsKxzNI1Rng2SxsEsnkK92Vh8CA Message-ID: Subject: Re: [PATCH 0/7] kcov: Introduce New Unique PC|EDGE|CMP Modes To: Marco Elver Cc: "Jiao, Joey" , Andrey Konovalov , Jonathan Corbet , Andrew Morton , Dennis Zhou , Tejun Heo , Christoph Lameter , Catalin Marinas , Will Deacon , kasan-dev@googlegroups.com, linux-kernel@vger.kernel.org, workflows@vger.kernel.org, linux-doc@vger.kernel.org, linux-mm@kvack.org, linux-arm-kernel@lists.infradead.org, kernel@quicinc.com Content-Type: text/plain; charset="UTF-8" X-Rspamd-Queue-Id: E560F20012 X-Stat-Signature: juu4bk85i6du9m4x6ad7hmwnhc34ge6b X-Rspam-User: X-Rspamd-Server: rspam11 X-HE-Tag: 1736852565-408320 X-HE-Meta: U2FsdGVkX18+AdqFFIUl6R4p1AffU+JxRlJqnCFDKsXCF0HvYJZPgRmgYYmwW2WnyzMtf62HU5nIGKmDzLRlFr+dVH0caE6tef+kkJYJSGj8batxgiNqaQG4dQ8V8aBkOq0eFN/+LD2g6EqBqoaJ4F292MIVtcAbmcxak9Jp9Odw2/octLNiaCzF79PTSRwGUSorZUX+fZGurYYnAfaZXQvy8ec/fQIkkjNex53Red2il4udGZ+nq0ybawJBoxjmThdYlGEsHy0MiLi9EyHNkBos+E1d8afxzrhejqSAhG7j/KMv9369/B64NrgxOmsBt2EPLIkehcQREF0YiVXPmT/oZBTM1UBl2zXt1XYr4AfRpqb7Xlu91WRAmAiRWSpiuSM/l/s1ydf/SPiRw4gBeL32qQ578Z4VYsNMdf0/loViC6aK8nifgx7lTcflZ5mHOPasDAzf7NayNzoaBBen/1x0Hl1FSG/Qw6OQGZMFr3aebCGXcKIjqM8oj+V5Hqi887i5oO/hJLESYjHYQxgvD3C3IPjrI05+WDh6cuc13/jxUH0AYVT93Rv/TvSi9M1TrNhxGK0SQYvhWaoEycydTKAxqKvJf+alU+gC791qX6om8qsN3D5xqWfc+fDsEhXEPk7Q8VXE96IlTt8ZUygAYH1IRDYT/tDmGm+En+n33JWkfMCu8MppYOeFdRpWmzK1ttJYuOY2JSpMXdut0LgDarP6OfLsUjAN2uaug4eu3MVbxY+nkhHRrMsvVi2fAq1Ai2f5iIeoZ5mZL4a68NEgO83QwqKpPaB3et/m/xlX+PFhop3pktuUPRmtdy8YddxxkYKJCBmW1Qs0ZHevIuE6BSVT7VQWNCN4ngkSdcqns4v1czU5mFfx2J24Yao/uEKXHFjUYRtFFJ9lyu8BbljJIs5YYP9ZPPeSHiMiwiosVL7sq8Xwh4+mMP5S/gikfJZ8FxqbQhAy9zn9IaHtFTm L2w9XjgF sgHb4/JFF1egaBRwZ+9U8J/kujQUATjsPGoHd2E6mXlOY3xYZysKtKephFhmFoZufFRUb+zSuZVe2ZINGAHegn+6gO0qvgvrqE++mfr/Tb3SZjPVdw4DvTg4QBiCaSmins/bUfhFyRYi8A4R91JSj0vDDCaWoiwy4ZEywVtZeze9yj8okhcHsFkqbxwHSwiy/0VFWWTSQlhFLV+A5akHCw859hyMqgvIOP/cDrA/vYp9LMNsx7nfj404849hWyadEAO2mAhhD2wZGw4fRs/pRtVyPvg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Tue, 14 Jan 2025 at 11:43, Marco Elver wrote: > On Tue, 14 Jan 2025 at 06:35, Jiao, Joey wrote: > > > > Hi, > > > > This patch series introduces new kcov unique modes: > > `KCOV_TRACE_UNIQ_[PC|EDGE|CMP]`, which are used to collect unique PC, EDGE, > > CMP information. > > > > Background > > ---------- > > > > In the current kcov implementation, when `__sanitizer_cov_trace_pc` is hit, > > the instruction pointer (IP) is stored sequentially in an area. Userspace > > programs then read this area to record covered PCs and calculate covered > > edges. However, recent syzkaller runs show that many syscalls likely have > > `pos > t->kcov_size`, leading to kcov overflow. To address this issue, we > > introduce new kcov unique modes. > > Overflow by how much? How much space is missing? > > > Solution Overview > > ----------------- > > > > 1. [P 1] Introduce `KCOV_TRACE_UNIQ_PC` Mode: > > - Export `KCOV_TRACE_UNIQ_PC` to userspace. > > - Add `kcov_map` struct to manage memory during the KCOV lifecycle. > > - `kcov_entry` struct as a hashtable entry containing unique PCs. > > - Use hashtable buckets to link `kcov_entry`. > > - Preallocate memory using genpool during KCOV initialization. > > - Move `area` inside `kcov_map` for easier management. > > - Use `jhash` for hash key calculation to support `KCOV_TRACE_UNIQ_CMP` > > mode. > > > > 2. [P 2-3] Introduce `KCOV_TRACE_UNIQ_EDGE` Mode: > > - Save `prev_pc` to calculate edges with the current IP. > > - Add unique edges to the hashmap. > > - Use a lower 12-bit mask to make hash independent of module offsets. > > - Distinguish areas for `KCOV_TRACE_UNIQ_PC` and `KCOV_TRACE_UNIQ_EDGE` > > modes using `offset` during mmap. > > - Support enabling `KCOV_TRACE_UNIQ_PC` and `KCOV_TRACE_UNIQ_EDGE` > > together. > > > > 3. [P 4] Introduce `KCOV_TRACE_UNIQ_CMP` Mode: > > - Shares the area with `KCOV_TRACE_UNIQ_PC`, making these modes > > exclusive. > > > > 4. [P 5] Add Example Code Documentation: > > - Provide examples for testing different modes: > > - `KCOV_TRACE_PC`: `./kcov` or `./kcov 0` > > - `KCOV_TRACE_CMP`: `./kcov 1` > > - `KCOV_TRACE_UNIQ_PC`: `./kcov 2` > > - `KCOV_TRACE_UNIQ_EDGE`: `./kcov 4` > > - `KCOV_TRACE_UNIQ_PC|KCOV_TRACE_UNIQ_EDGE`: `./kcov 6` > > - `KCOV_TRACE_UNIQ_CMP`: `./kcov 8` > > > > 5. [P 6-7] Disable KCOV Instrumentation: > > - Disable instrumentation like genpool to prevent recursive calls. > > > > Caveats > > ------- > > > > The userspace program has been tested on Qemu x86_64 and two real Android > > phones with different ARM64 chips. More syzkaller-compatible tests have > > been conducted. However, due to limited knowledge of other platforms, > > assistance from those with access to other systems is needed. > > > > Results and Analysis > > -------------------- > > > > 1. KMEMLEAK Test on Qemu x86_64: > > - No memory leaks found during the `kcov` program run. > > > > 2. KCSAN Test on Qemu x86_64: > > - No KCSAN issues found during the `kcov` program run. > > > > 3. Existing Syzkaller on Qemu x86_64 and Real ARM64 Device: > > - Syzkaller can fuzz, show coverage, and find bugs. Adjusting `procs` > > and `vm mem` settings can avoid OOM issues caused by genpool in the > > patches, so `procs:4 + vm:2GB` or `procs:4 + vm:2GB` are used for > > Qemu x86_64. > > - `procs:8` is kept on Real ARM64 Device with 12GB/16GB mem. > > > > 4. Modified Syzkaller to Support New KCOV Unique Modes: > > - Syzkaller runs fine on both Qemu x86_64 and ARM64 real devices. > > Limited `Cover overflows` and `Comps overflows` observed. > > > > 5. Modified Syzkaller + Upstream Kernel Without Patch Series: > > - Not tested. The modified syzkaller will fall back to `KCOV_TRACE_PC` > > or `KCOV_TRACE_CMP` if `ioctl` fails for Unique mode. > > > > Possible Further Enhancements > > ----------------------------- > > > > 1. Test more cases and setups, including those in syzbot. > > 2. Ensure `hash_for_each_possible_rcu` is protected for reentrance > > and atomicity. > > 3. Find a simpler and more efficient way to store unique coverage. > > > > Conclusion > > ---------- > > > > These patches add new kcov unique modes to mitigate the kcov overflow > > issue, compatible with both existing and new syzkaller versions. > > Thanks for the analysis, it's clearer now. > > However, the new design you introduce here adds lots of complexity. > Answering the question of how much overflow is happening, might give > better clues if this is the best design or not. Because if the > overflow amount is relatively small, a better design (IMHO) might be > simply implementing a compression scheme, e.g. a simple delta > encoding. Joey, do you have corresponding patches for syzkaller? I wonder how the integration looks like, in particular when/how these maps are cleared.