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 A8748E77188 for ; Tue, 14 Jan 2025 10:43:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 434CF6B0089; Tue, 14 Jan 2025 05:43:48 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 3BE1B6B008A; Tue, 14 Jan 2025 05:43:48 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 285BA6B008C; Tue, 14 Jan 2025 05:43:48 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 04D4C6B0089 for ; Tue, 14 Jan 2025 05:43:47 -0500 (EST) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id A2A63A084C for ; Tue, 14 Jan 2025 10:43:47 +0000 (UTC) X-FDA: 83005721694.11.A2A988B Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) by imf15.hostedemail.com (Postfix) with ESMTP id C47A3A0009 for ; Tue, 14 Jan 2025 10:43:45 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=1JssP1a+; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf15.hostedemail.com: domain of elver@google.com designates 209.85.216.43 as permitted sender) smtp.mailfrom=elver@google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1736851425; 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=U+iFfCSA0esMLhZDHY92zW4RJncb7ADni12U1qFlLKc=; b=W9Q10ZyQxQex5z27R/49n8uXUgLJ/1afFq96ZlUzPGqh013HfkEF7J7P6EaA+5z9PiyZTE 2V4oEFKu+GMCS0q69DBGiYde0empjrQ2xa3VAxhD7k/YvQ/Ve93jX5Y1cVWbwFOl6K6BsV n6GLHzUqVtsPT1fAJYiYIGdL3kLA8ng= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1736851425; a=rsa-sha256; cv=none; b=kmbRXOe+NsGpHafyLJtKuapEimZ8Kw/idliRvd6SRy0hodp07sfVECNU0W3Wm5v515UoCs o6MyUBVj1FbBUmXLMF4vZPmPHq1FTIqgfqHzQFyV/nUDR5LVHed9M+rWhr6Odk0ZEwGSfa A4yGjDUBe4uARM1zI4pUtWpqD1E7IEI= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=1JssP1a+; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf15.hostedemail.com: domain of elver@google.com designates 209.85.216.43 as permitted sender) smtp.mailfrom=elver@google.com Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-2ef8c012913so6656316a91.3 for ; Tue, 14 Jan 2025 02:43:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1736851424; x=1737456224; 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=U+iFfCSA0esMLhZDHY92zW4RJncb7ADni12U1qFlLKc=; b=1JssP1a+6/G8VR0tfFgSTf4gXW/HzHKlsHrkhoN5/0kykHz4ahxep3p1x4OpupwU7c y0P1xVsffhVgjl801lx3lhGvQGXv0tMt4OSjqOeAxPvmDlDh5Ul4cVKDdxKOXdkn6F41 Hdb5dS9rTEBfhctVVFOz+ajGbZrFr07hWKHyrFTFuzJKNqq7SNtLaWPp69PtZzR7lnQo l+fPZEtvNJ1wd0WX8oJ9mZ7vldmMlwk2JUmA1E2Kh1nWF3fLL+CVf7IRqxfXCB2l01e3 f9rgy/QjORt/aYeoQwluWItzsoy7d/dhZDFOkCYwhk4nONcZ/zTJVEUs8REaKxvKMTX1 i5Xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736851424; x=1737456224; 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=U+iFfCSA0esMLhZDHY92zW4RJncb7ADni12U1qFlLKc=; b=G3QfBlGFf/DCYrgQzK/tRuuI3ZbOS0yD/D3OgnUtpal/UKLgKoDqCoGYZYkDdpRYIY AfQ3ACjkDm3AyzvBtXmlIQjo1gDFO+1sKzAfJ0hSocV29IW0W4I/QBRoUdwPXTL4mE1Z Y6BldOxqGAyHKddnO+w/MDZ5X+75eMMVwXO2lCthGEzrZeFoL7LjdjmfULfzKhcRPLWm RfvI1BSjkw9qJxKwflm9OqWbkbwz9I+A4WuMTdqMx7OwlrJQwhGTqcSfJi9wFvwuyPec PpCwVeQt2AkVHK0wSjRoOnzT3HeTNkArrjB3sK9yA6OquTw/IXTNQvp2Nihg7rDkUFq3 E/Dg== X-Forwarded-Encrypted: i=1; AJvYcCXKl8EOMqM96tBaRsTJqIaTbWTxe538a06JqN3h2buo/lOrZOM9qLYy7u5Ldt+JttXvfSx9eX9zLA==@kvack.org X-Gm-Message-State: AOJu0YxL7so+DwTz4n4tGRDdfkzArgm2huqfdMCjfsNCZ/s0N1alYjFS kDVS+lzIUeja2odw83BQ5I3lHgbNattaY5aH7r3+Hoev7vcCeFRDP1/1tFedxnyIyPOXZCQ2nZr jzpZT4JkaVs5OlW27bNFqv3tj4Ua+A5DRsKYv X-Gm-Gg: ASbGncuArpoACCkiZ++n/Wcd9lX6DeXH3RPvbvmmnXXErrva38UBcdsetQh1ebc6W0j EqLnRIqzbOguXoatqH/jeYOT9IAblFLcdMjD2fF9WOWLA5h9qPUIwr+yCaNkaBZBDQKw3 X-Google-Smtp-Source: AGHT+IGczXH0RwSvDlb2KRoPip36lSqxyB+OuiMrmApQOWno0b47AQpdfRInLeDgapSvPtkwUC9nyMn+0RAYGxD5H2c= X-Received: by 2002:a17:90b:540f:b0:2ee:48bf:7dc3 with SMTP id 98e67ed59e1d1-2f548eb321emr37372999a91.15.1736851424249; Tue, 14 Jan 2025 02:43:44 -0800 (PST) MIME-Version: 1.0 References: <20250114-kcov-v1-0-004294b931a2@quicinc.com> In-Reply-To: <20250114-kcov-v1-0-004294b931a2@quicinc.com> From: Marco Elver Date: Tue, 14 Jan 2025 11:43:08 +0100 X-Gm-Features: AbW1kvaVa5-9nPmDbOZJ9N5LtR4pKYs5_Kxyb15S0vct137T7GGOlb18swg2wtM Message-ID: Subject: Re: [PATCH 0/7] kcov: Introduce New Unique PC|EDGE|CMP Modes To: "Jiao, Joey" Cc: Dmitry Vyukov , 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-Stat-Signature: 8prpao6t4wa9qofut3ugbe5657uce63f X-Rspamd-Queue-Id: C47A3A0009 X-Rspam-User: X-Rspamd-Server: rspam01 X-HE-Tag: 1736851425-965011 X-HE-Meta: U2FsdGVkX1/jKzPhvjqe2lfYsaeV8JE+isb2boKIvAxiTDizdfGfhcy9VgZ1oV+CHiBFlcXZud2REF1lLlSUoB59sIz+KfpIMoK7n6qW1m9745KpsekgxEfrpYT0c9FOCN+0eX0euFgYqPJSd7MXdMZSl/c72KwtEZd9euSBc9sclojSW3EEv5bBNlVbIEhVJ90rrEmxlsfmoUYCIGYY/q55bDB8ceKkmskFb0GPPVSobiefobayv/CR1KqZYmy60C2yaEqI1+7c4CD1SeGpsxz7/7QvpuCdPDQwv9jyik+5O1drO/KJDjnhQJLYw/0s+XNTJzlubcmrnV1yHdXLV09WFpsK33pgaw3iwHlbK4pkMvQCc+ZhpQy0RKf0V4fgzfNq40I8lvhZEV0gDHCMPqdhJMDdLfYKjn/tKgatfxPQHTdYjuxIvY04OFTICKqb8LDG9GvtysFFpIP/y5B41G4zFF0V/g9ccyR36bYwaaozsdxeuS+iP5V1iZKhh8c1o9wB5Ba9Zn/Xazb1ZIp2T0/1AEqnvtdvUb34UnjqdXIGHKQ+Pj6sW5oyWCKmZJZyAMGBperfPoIGUssNMD3GS3YcOIEDyv1aHlaqG1jSpy5buDOGxB403i1cP24C/8oeVoijnz5xLM43jADcQwEg27GFWtn7BkNvZMRqmJuD7T6P/fBmv+wSXrbQSk1VRhb1c1cq0cBWwoxyeS+ryR0DhonMKXcQXRr/IXxurSm3/79SY6PM7vb1NA7tPe+l+J426gAQI4LpGX0YM+tlCVNSBMRq3Yj4o/bgVUJyDP9PRu+HAHRrJ84KHsNdtWrjg6qX/4ptaIeMOOnPxf+YrVwITndlaBVAR7dV0IeTUwDQyNInRJVwgRXYFivyL1G85Gv4BHOEU3G1oTu0DrC+uB20hSRxggL3T1RUc3zzrLbojTN/gngifqZOViDA0vhTBcKkspaEeJK+Z6ELLjRWXft 6z6EcLro gPF5C3K/LMnSTBmJ6KDiBCzC68F0Otw+QRaMqM+AhW+8cGeGkn9yDnYSw0CtNHUcY/I1lalqDKFH9Dy4sVQcci+Levqo36k7mm4qQatnwm7qtQ65wvvKinJju+hw05cpI5/8UC1xFotKY5bCn9B5QHcmLNfJk9Gnme822RC9NY19Znkemh8UCUnh6m2IHZMCgG0KYBQfkEzNUz0dD+FQzTA0IRBELIcDewcnLQpZdgRqBhAnOIqbZUXaa/mFSaY8SXSMV 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 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. Thanks, -- Marco