From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932066AbWFMKta (ORCPT ); Tue, 13 Jun 2006 06:49:30 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1750933AbWFMKta (ORCPT ); Tue, 13 Jun 2006 06:49:30 -0400 Received: from nz-out-0102.google.com ([64.233.162.206]:23677 "EHLO nz-out-0102.google.com") by vger.kernel.org with ESMTP id S1750926AbWFMKt3 (ORCPT ); Tue, 13 Jun 2006 06:49:29 -0400 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=MHvV7gmnNBlNx2xunQvisCaPjCfV8eY5q7ZfW3JsYf+Z+3oBdMFFuX1uwe1dBmM4rTT9iwPY+vej4ka2GAPGJIqinajdo0km08lscx50y0uSDy5rSnoZFrO+rGQ1N0RVaLw0rRLql9yWG+dTCC86zo9qMKc2C5RqQOBKI5De8lU= Message-ID: Date: Tue, 13 Jun 2006 11:49:28 +0100 From: "Catalin Marinas" To: "Ingo Molnar" Subject: Re: [PATCH 2.6.17-rc6 7/9] Remove some of the kmemleak false positives Cc: "Pekka J Enberg" , linux-kernel@vger.kernel.org In-Reply-To: <20060613072646.GA17978@elte.hu> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20060611111815.8641.7879.stgit@localhost.localdomain> <20060611112156.8641.94787.stgit@localhost.localdomain> <84144f020606112219m445a3ccas7a95c7339ca5fa10@mail.gmail.com> <20060612105345.GA8418@elte.hu> <20060612192227.GA5497@elte.hu> <20060613072646.GA17978@elte.hu> Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org On 13/06/06, Ingo Molnar wrote: > > * Pekka J Enberg wrote: > > > Hi Ingo, > > > > On Mon, 12 Jun 2006, Ingo Molnar wrote: > > > i dont know - i feel uneasy about the 'any pointer' method - it has a > > > high potential for false negatives, especially for structures that > > > contain strings (or other random data), etc. > > > > Is that a problem in practice? Structures that contain data are > > usually allocated from the slab. There needs to be a link to that > > struct from the gc roots to get a false negative. Or am I missing > > something here? > > you should think of this in terms of a 'graph of data', where each node > is a block of memory. The edges between nodes are represented by > pointers. The graph roots from .data/bss, but it may go indefinitely > into dynamically allocated blocks as well - just think of a hash-list > where the hash list table is in .data, but all the chain entries are in > allocated blocks and the chaining can be arbitrarily deep. [...] Nice description, I should add it to the kmemleak doc :-) > Currently kmemleak does not track the per-block position of 'outgoing > pointers': it assumes that all fields within a block may be an outgoing > pointer. This is a source of false negatives. (fields that do not > contain a real pointer might accidentally contain a value that is > interpreted as a false edge - falsely connecting a leaked block to the > graph.) That's correct but it might not be a real issue in practice. Many people use the Boehm's GC and haven't complained about the amount of false negatives (AFAIK, there is even a proposal to include it in the next C++ standard). > Kmemleak does recognize 'incoming pointers' via the offsetof tracking > method, but it's limited in that it is not a type-accurate method > either: it tracks per-size offsets, so two types accidentally having the > same size merges their 'possible incoming pointer offset' lists, which > introduces false negatives. (a pointer may be considered an incoming > edge while in reality the pointer is not validly pointing into this > structure) The number of collisions would need to be investigated. On my system, there are 158 distinct sizeof values generated by container_of. Of this, 90 have at least two aliases (incoming pointer offsets). I'm not sure how many different structures are in the kernel but I can't find an easy (gcc magic) way to get a unique id for a type (apart from modifying all the container_of calls and add a 4th argument - maybe a string with the name of the type). > The full matching that was suggested before would further weaken the > 'incoming pointers' logic and would introduce yet another source of > false negatives: we'd match every block pointer against every possible > target address that points to within another block. That's correct. > My suggestion would be to attempt to achieve perfect matches: annotate > structures to figure out the offset of pointers, and thus to figure out > the precise source addresses and a precise list of valid target > addresses. This is a quite elaborate task to pull off though, and i'm > not sure it's possible without intolerable maintainance overhead, but we > should consider it nevertheless. It will also be _much_ faster, because > per block we'd only have to scan a handful of outgoing pointers. The problem would be simpler if you get a reliable typeid. If we consider the sizeof method, a script could scan the kernel and generate a list of sizeof-pointer_offset pairs which is added to a radix tree (similar to the aliases tree we have) at boot time. But this would assume adding the memleak_padding() call not only for incoming pointers but also for outgoing ones. The method, however, would eliminate the need for annotating each structure in the kernel. > This also means that by default we'd have no false positives at all, You can still have a scenario like this - a pointer is freed but the value remains in a valid member; it is afterwards re-allocated and leaks but the value is found in a previous allocation. I think it's a very low risk for this to happen and not worth the hassle. > but > that there is a capable annotation method to reduce the amount of false > negatives, in a gradual and managable way - down to zero if everything > is annotated. I'm not sure this could be achieved in a maintainable way, at least not without support from the compiler. -- Catalin