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 X-Spam-Level: X-Spam-Status: No, score=-8.8 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 20E7BC43441 for ; Wed, 28 Nov 2018 23:44:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C3FCB206B2 for ; Wed, 28 Nov 2018 23:44:33 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=mailprotect.be header.i=@mailprotect.be header.b="Zp15/HcI" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org C3FCB206B2 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=acm.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727725AbeK2Krw (ORCPT ); Thu, 29 Nov 2018 05:47:52 -0500 Received: from out002.mailprotect.be ([83.217.72.86]:60227 "EHLO out002.mailprotect.be" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727651AbeK2Krv (ORCPT ); Thu, 29 Nov 2018 05:47:51 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mailprotect.be; s=mail; h=Content-Transfer-Encoding:MIME-Version:References :In-Reply-To:Message-Id:Date:Subject:Cc:To:From:reply-to:sender:bcc: content-type; bh=AVe7X97FfVCptP+oSX9PqNr0U0iqxffWT8hI2J35IY0=; b=Zp15/HcIGLcf JginfnZ4qC7FS3iW8laaiWXE+eijetzAJOuj4rUMCbGHOXHiCSJ7B19aNPtbsuUMQ8X8lBb2OJ64T jmrEw2u4g4GF57G2fJGSfV0WGSg0w4YAoONjhbzrR+jHDAZG6xMTWjQM4iL38arIkHTHeKCmkbK4n qqp1Oi6cz2V+a1oeD0hkrmKuLnKppM05DIJcDgQb6oGBZi54FqgfvyrgHj/FuY8RawpmppEYWJng3 q3Teo4Ja7DS30FC5Np650VzyzlEgUhNIp1QiwK8n9WuQ9GfMCeqoTrGXjdQyKC/jgpqQRosvzYez4 ZOX0IX0oCZe6j7fuooCRYQ==; Received: from smtp-auth.mailprotect.be ([178.208.39.159]) by com-mpt-out002.mailprotect.be with esmtp (Exim 4.89) (envelope-from ) id 1gS9VF-000Fm0-RG; Thu, 29 Nov 2018 00:44:22 +0100 Received: from desktop-bart.svl.corp.google.com (unknown [104.133.8.89]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by smtp-auth.mailprotect.be (Postfix) with ESMTPSA id B45A8C11D1; Thu, 29 Nov 2018 00:44:19 +0100 (CET) From: Bart Van Assche To: mingo@redhat.com Cc: peterz@infradead.org, tj@kernel.org, johannes.berg@intel.com, linux-kernel@vger.kernel.org, Bart Van Assche Subject: [PATCH 25/27] locking/lockdep: Add support for dynamic keys Date: Wed, 28 Nov 2018 15:43:23 -0800 Message-Id: <20181128234325.110011-26-bvanassche@acm.org> X-Mailer: git-send-email 2.20.0.rc0.387.gc7a69e6b6c-goog In-Reply-To: <20181128234325.110011-1-bvanassche@acm.org> References: <20181128234325.110011-1-bvanassche@acm.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Originating-IP: 178.208.39.159 X-SpamExperts-Domain: mailprotect.be X-SpamExperts-Username: 178.208.39.128/27 Authentication-Results: mailprotect.be; auth=pass smtp.auth=178.208.39.128/27@mailprotect.be X-SpamExperts-Outgoing-Class: ham X-SpamExperts-Outgoing-Evidence: SB/global_tokens (0.0091651940514) X-Recommended-Action: accept X-Filter-ID: EX5BVjFpneJeBchSMxfU5vSk71anxSJ+eLy/nvVZCE9602E9L7XzfQH6nu9C/Fh9KJzpNe6xgvOx q3u0UDjvO1tLifGj39bI0bcPyaJsYTb/+zriNZuqQk0xRpGwjn+MTR8dtByWYYhgj25jR+mEA3YO AtfhCcV13BpIh8lqRXSSiFVwqwU9VgKUrYQ0lqWyB41b1wEpWO6ik9HITpMsqebHcXK5F5szpMR3 ucwUCaulpCLw+Xb9GLNy0GASgpn9t8C9mOBdONdnsxgsk1D2p09kN7MM31r8n6t5T2S20aXquTa3 0lhsPhd1aLrBp/LZq2ydL+V39l/HBScm+SV6be+d9aVwS6cHCn1lU19HAi33Iz6Zvpm8cPQnANwk DQ5BNCNwpGn8jfSb3NCl2WUq09dCYgcgr835yVjKQZA6hJL1LiMHCxRezvZaFOrUVh8zaVyj66M1 yz85ZZhpUrhTRbASVYnBhdKUnGmBdHG7BUn2dK6UtSEdwn3yFtfkzf2g6K04cY809V1JdCwiLdDQ Dow7RSjhmGOVelXQaHGaUkBvyMjbyNpr4xR6RL2C9+qlIny++hg9dJLqN5zmWqF/oNe6FVV7drXD mtOldfpWzeUCaRHvx+uLGHS3n3Y0pMd0ZyCgxZHINA6A5+7T9o6by6wCf9/ixXi9QE6xc2MJdJIs WkULIn/2FBvF31UHbsndehIqUczFWeS6sE8e1b5/UlaX0Ao5X99TlizdjWjXhcukjPvPb2ztUwUU F4ekbSpuNzlrea/7iuldgAMiBvdjMePjHvSRX26LLkNlzX14Ub4HmFDqewO9xyOqCYO8P1aHcsG0 kWCiESR44kXyAcFBnvq0JaXhRWKyqy0OhbkmMxu2AdrcZPAiQvyjIZ4LQqnqqLEDUnB02oJPHAlf IubJYzA0XAoGECHs14pjPDDBgamvNiA5kjk+kUt44s0jst5fih4ywAIfIdz9r5vpA/Yw0HZ1zCZg riVyrkCho9oJ7YFuhWzfuvHd4y0L/HyfN5U858I8R2vIYlYbA7G/CY3eeSCFRiwDn8j3yWGHtM7w dRonBy/PpUxgSFRPcWxJF+/beJHmCfSNEcGdfFKs5M18F1x96tlonSt5Ig9mwLw4vXsdf68W0InH /+bTMKNm38MHV+diwrlXuxzeO2WnJyd7g8lLLKZgdBo3YHaSgbLEg7M4I+zZPnIX6k9TnzH5sZcr MS+4ayUpOtEhdxekWDmK9g== X-Report-Abuse-To: spam@com-mpt-mgt001.mailprotect.be Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org A shortcoming of the current lockdep implementation is that it requires lock keys to be allocated statically. That forces certain lock objects to share lock keys. Since lock dependency analysis groups lock objects per key sharing lock keys can cause false positive lockdep reports. Make it possible to avoid such false positive reports by allowing lock keys to be allocated dynamically. Require that dynamically allocated lock keys are registered before use by calling lockdep_register_key(). Complain about attempts to register the same lock key pointer twice without calling lockdep_unregister_key() between successive registration calls. Signed-off-by: Bart Van Assche --- include/linux/lockdep.h | 13 ++++- kernel/locking/lockdep.c | 121 ++++++++++++++++++++++++++++++++++++--- 2 files changed, 123 insertions(+), 11 deletions(-) diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h index 01e55fca7c2c..bd6bfad66382 100644 --- a/include/linux/lockdep.h +++ b/include/linux/lockdep.h @@ -46,15 +46,19 @@ extern int lock_stat; #define NR_LOCKDEP_CACHING_CLASSES 2 /* - * Lock-classes are keyed via unique addresses, by embedding the - * lockclass-key into the kernel (or module) .data section. (For - * static locks we use the lock address itself as the key.) + * A lockdep key is associated with each lock object. For static locks we use + * the lock address itself as the key. Dynamically allocated lock objects can + * have a statically or dynamically allocated key. Dynamically allocated lock + * keys must be registered before being used and must be unregistered before + * the key memory is freed. */ struct lockdep_subclass_key { char __one_byte; } __attribute__ ((__packed__)); +/* hash_entry is used to keep track of dynamically allocated keys. */ struct lock_class_key { + struct hlist_node hash_entry; struct lockdep_subclass_key subkeys[MAX_LOCKDEP_SUBCLASSES]; }; @@ -280,6 +284,9 @@ extern asmlinkage void lockdep_sys_exit(void); extern void lockdep_off(void); extern void lockdep_on(void); +extern void lockdep_register_key(struct lock_class_key *key); +extern void lockdep_unregister_key(struct lock_class_key *key); + /* * These methods are used by specific locking variants (spinlocks, * rwlocks, mutexes and rwsems) to pass init/acquire/release events diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c index 0e273731d028..213153b10951 100644 --- a/kernel/locking/lockdep.c +++ b/kernel/locking/lockdep.c @@ -142,6 +142,9 @@ static LIST_HEAD(free_list_entries); * free_lock_classes points at the first free element. These elements are * linked together by the lock_entry member in struct lock_class. */ +#define KEYHASH_BITS (MAX_LOCKDEP_KEYS_BITS - 1) +#define KEYHASH_SIZE (1UL << KEYHASH_BITS) +static struct hlist_head lock_keys_hash[KEYHASH_SIZE]; unsigned long nr_lock_classes; static struct lock_class lock_classes[MAX_LOCKDEP_KEYS]; static LIST_HEAD(free_lock_classes); @@ -602,7 +605,7 @@ static int very_verbose(struct lock_class *class) * Is this the address of a static object: */ #ifdef __KERNEL__ -static int static_obj(void *obj) +static int static_obj(const void *obj) { unsigned long start = (unsigned long) &_stext, end = (unsigned long) &_end, @@ -881,6 +884,70 @@ static void init_lists(void) list_add_tail(&list_entries[i].alloc_entry, &free_list_entries); } +static inline struct hlist_head *keyhashentry(const struct lock_class_key *key) +{ + unsigned long hash = hash_long((uintptr_t)key, KEYHASH_BITS); + + return lock_keys_hash + hash; +} + +/* + * Register a dynamically allocated key. + */ +void lockdep_register_key(struct lock_class_key *key) +{ + struct hlist_head *hash_head; + struct lock_class_key *k; + unsigned long flags; + + if (WARN_ON_ONCE(static_obj(key))) + return; + hash_head = keyhashentry(key); + raw_local_irq_save(flags); + if (!graph_lock()) + goto restore_irqs; + hlist_for_each_entry_rcu(k, hash_head, hash_entry) { + if (WARN_ON_ONCE(k == key)) + goto out_unlock; + } + hlist_add_head_rcu(&key->hash_entry, hash_head); +out_unlock: + graph_unlock(); +restore_irqs: + raw_local_irq_restore(flags); +} +EXPORT_SYMBOL_GPL(lockdep_register_key); + +/* + * Check whether a key has been registered as a dynamic key. Must not be called + * from interrupt context. + */ +static bool is_dynamic_key(const struct lock_class_key *key) +{ + struct hlist_head *hash_head; + struct lock_class_key *k; + unsigned long flags; + bool found = false; + + if (WARN_ON_ONCE(static_obj(key))) + return false; + hash_head = keyhashentry(key); + raw_local_irq_save(flags); + if (!graph_lock()) + goto restore_irqs; + hlist_for_each_entry_rcu(k, hash_head, hash_entry) { + if (k == key) { + found = true; + break; + } + } + graph_unlock(); +restore_irqs: + raw_local_irq_restore(flags); + + return found; +} + /* * Register a lock's class in the hash-table, if the class is not present * yet. Otherwise we look it up. We cache the result in the lock object @@ -905,7 +972,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force) if (!lock->key) { if (!assign_lock_key(lock)) return NULL; - } else if (!static_obj(lock->key)) { + } else if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) { return NULL; } @@ -3284,13 +3351,13 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name, if (DEBUG_LOCKS_WARN_ON(!key)) return; /* - * Sanity check, the lock-class key must be persistent: + * Sanity check, the lock-class key must either have been allocated + * statically or must have been registered as a dynamic key. */ - if (!static_obj(key)) { - printk("BUG: key %px not in .data!\n", key); - /* - * What it says above ^^^^^, I suggest you read it. - */ + if (!static_obj(key) && !is_dynamic_key(key)) { + if (debug_locks) + printk(KERN_INFO "BUG: key %px has not been registered!\n", + key); DEBUG_LOCKS_WARN_ON(1); return; } @@ -4510,6 +4577,44 @@ void lockdep_free_key_range(void *start, unsigned long size) free_zapped_classes(&zapped_classes); } + +/* + * Unregister a dynamically allocated key. Must not be called from interrupt + * context. The caller must ensure that freeing @key only happens after an RCU + * grace period. + */ +void lockdep_unregister_key(struct lock_class_key *key) +{ + struct list_head zapped_classes; + struct hlist_head *hash_head = keyhashentry(key); + struct lock_class_key *k; + unsigned long flags; + bool found = false; + + if (WARN_ON_ONCE(static_obj(key))) + return; + + __lockdep_free_key_range(&zapped_classes, key, 1); + + raw_local_irq_save(flags); + if (!graph_lock()) + goto restore_irqs; + hlist_for_each_entry_rcu(k, hash_head, hash_entry) { + if (k == key) { + hlist_del_rcu(&k->hash_entry); + found = true; + break; + } + } + WARN_ON_ONCE(!found); + graph_unlock(); +restore_irqs: + raw_local_irq_restore(flags); + + free_zapped_classes(&zapped_classes); +} +EXPORT_SYMBOL_GPL(lockdep_unregister_key); + /* * Check whether any element of the @lock->class_cache[] array refers to a * registered lock class. The caller must hold either the graph lock or the -- 2.20.0.rc0.387.gc7a69e6b6c-goog