From patchwork Thu Dec 22 08:36:08 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Wilson X-Patchwork-Id: 9484405 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 2D679601D2 for ; Thu, 22 Dec 2016 08:37:37 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2995F27FA6 for ; Thu, 22 Dec 2016 08:37:37 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1E77D283A6; Thu, 22 Dec 2016 08:37:37 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id BE50F27FA6 for ; Thu, 22 Dec 2016 08:37:36 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 570026F17A; Thu, 22 Dec 2016 08:37:34 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from mail-wm0-x244.google.com (mail-wm0-x244.google.com [IPv6:2a00:1450:400c:c09::244]) by gabe.freedesktop.org (Postfix) with ESMTPS id 316236F171; Thu, 22 Dec 2016 08:36:53 +0000 (UTC) Received: by mail-wm0-x244.google.com with SMTP id u144so34758614wmu.0; Thu, 22 Dec 2016 00:36:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=qv1EszbJpsintHdAoUNe/+Z5ObJ3HfTBdGUZqwEhdd8=; b=BJpeuq+5UyetvAHmgIHwc9wkNdBdh7r0OhgPdFmmJIPiO+7mzHarDYONqwytovbfQu e4LqeCu++bsCZh2lQ9uZeG1L3022KTpGS9terUNJhL0MUcwuyUUcgPZUIqf0vKnNobkS rAh3LaZbBcz64LoM8AdjHwZNhVVoHMCFznYB/kMuw1/HqBHAOSoGJZL70m+7VhOaZLbr cMD3ax6C0N8pIT3t19jEIJZj0yIvAWdcOFxeayFV6/ih/OcVMSIT2Do6fAziix6WZSoy bLDs0lNxdXNCHr4H90OHhFI0hj0/84CIcMwpLg1qOJdNSe6MrtLeUG3Upxc3lBp5w586 32pw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=qv1EszbJpsintHdAoUNe/+Z5ObJ3HfTBdGUZqwEhdd8=; b=dIfAG38IMxNpgWxFsr3LFDM4YcQQjkN5txH/+Yv/T/9shH2w+mA83l7YElKya1936L BgPQn7e2LKhASgge7rv7UHkHxa6FSltB7TPJ3Pyf/5lZgwMJIX+vCloqrQMgli+QEmeV syx7x6XQ9G6KbKvMckUsg6U9MMnkgZMMOQQLuZPRBU5Udulpbzw1aKutfqwWJ4yVUxdg bqHc4AAqLFfINFNC9aRO/ND+pbzl/60ndFBoEfjwPv9N4Oqkj0mTg+040wVFC6PNFDqK Ni7KjEfjQlN0HY2SCqg5rhj06xRqnvlNVAaRpfvR+k4xUffPB5X4p4ftAEPZqj/RG+Ri H3mQ== X-Gm-Message-State: AIkVDXJ6Yf6eIKUrMgvqN8rLIRT2znqmqMnOAUFVEvReWy7YbUgC196byc0OShOnzo7+IQ== X-Received: by 10.28.71.137 with SMTP id m9mr10036562wmi.88.1482395811166; Thu, 22 Dec 2016 00:36:51 -0800 (PST) Received: from haswell.alporthouse.com ([78.156.65.138]) by smtp.gmail.com with ESMTPSA id di9sm34442318wjc.37.2016.12.22.00.36.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 22 Dec 2016 00:36:50 -0800 (PST) From: Chris Wilson To: dri-devel@lists.freedesktop.org Subject: [PATCH v4 05/38] drm: Add a simple generator of random permutations Date: Thu, 22 Dec 2016 08:36:08 +0000 Message-Id: <20161222083641.2691-6-chris@chris-wilson.co.uk> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20161222083641.2691-1-chris@chris-wilson.co.uk> References: <20161222083641.2691-1-chris@chris-wilson.co.uk> Cc: intel-gfx@lists.freedesktop.org, Joonas Lahtinen X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP When testing, we want a random but yet reproducible order in which to process elements. Here we create an array which is a random (using the Tausworthe PRNG) permutation of the order in which to execute. Note these are simple helpers intended to be merged upstream in lib/ v2: Tidier code by David Herrmann v3: Add reminder that this code is intended to be temporary, with at least the bulk of the prandom changes going to lib/ Signed-off-by: Chris Wilson Cc: Joonas Lahtinen Cc: David Herrmann Reviewed-by: Joonas Lahtinen --- drivers/gpu/drm/Kconfig | 4 ++++ drivers/gpu/drm/Makefile | 1 + drivers/gpu/drm/lib/drm_random.c | 41 ++++++++++++++++++++++++++++++++++++++++ drivers/gpu/drm/lib/drm_random.h | 25 ++++++++++++++++++++++++ 4 files changed, 71 insertions(+) create mode 100644 drivers/gpu/drm/lib/drm_random.c create mode 100644 drivers/gpu/drm/lib/drm_random.h diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig index ebfe8404c25f..45a1c7468e88 100644 --- a/drivers/gpu/drm/Kconfig +++ b/drivers/gpu/drm/Kconfig @@ -321,3 +321,7 @@ config DRM_SAVAGE chipset. If M is selected the module will be called savage. endif # DRM_LEGACY + +config DRM_LIB_RANDOM + bool + default n diff --git a/drivers/gpu/drm/Makefile b/drivers/gpu/drm/Makefile index b9ae4280de9d..6bb416360ae4 100644 --- a/drivers/gpu/drm/Makefile +++ b/drivers/gpu/drm/Makefile @@ -18,6 +18,7 @@ drm-y := drm_auth.o drm_bufs.o drm_cache.o \ drm_plane.o drm_color_mgmt.o drm_print.o \ drm_dumb_buffers.o drm_mode_config.o +drm-$(CONFIG_DRM_LIB_RANDOM) += lib/drm_random.o drm-$(CONFIG_COMPAT) += drm_ioc32.o drm-$(CONFIG_DRM_GEM_CMA_HELPER) += drm_gem_cma_helper.o drm-$(CONFIG_PCI) += ati_pcigart.o diff --git a/drivers/gpu/drm/lib/drm_random.c b/drivers/gpu/drm/lib/drm_random.c new file mode 100644 index 000000000000..7b12a68c3b54 --- /dev/null +++ b/drivers/gpu/drm/lib/drm_random.c @@ -0,0 +1,41 @@ +#include +#include +#include +#include +#include + +#include "drm_random.h" + +static inline u32 drm_prandom_u32_max_state(u32 ep_ro, struct rnd_state *state) +{ + return upper_32_bits((u64)prandom_u32_state(state) * ep_ro); +} + +void drm_random_reorder(unsigned int *order, unsigned int count, + struct rnd_state *state) +{ + unsigned int i, j; + + for (i = 0; i < count; ++i) { + BUILD_BUG_ON(sizeof(unsigned int) > sizeof(u32)); + j = drm_prandom_u32_max_state(count, state); + swap(order[i], order[j]); + } +} +EXPORT_SYMBOL(drm_random_reorder); + +unsigned int *drm_random_order(unsigned int count, struct rnd_state *state) +{ + unsigned int *order, i; + + order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY); + if (!order) + return order; + + for (i = 0; i < count; i++) + order[i] = i; + + drm_random_reorder(order, count, state); + return order; +} +EXPORT_SYMBOL(drm_random_order); diff --git a/drivers/gpu/drm/lib/drm_random.h b/drivers/gpu/drm/lib/drm_random.h new file mode 100644 index 000000000000..a78644bea7f9 --- /dev/null +++ b/drivers/gpu/drm/lib/drm_random.h @@ -0,0 +1,25 @@ +#ifndef __DRM_RANDOM_H__ +#define __DRM_RANDOM_H__ + +/* This is a temporary home for a couple of utility functions that should + * be transposed to lib/ at the earliest convenience. + */ + +#include + +#define DRM_RND_STATE_INITIALIZER(seed__) ({ \ + struct rnd_state state__; \ + prandom_seed_state(&state__, (seed__)); \ + state__; \ +}) + +#define DRM_RND_STATE(name__, seed__) \ + struct rnd_state name__ = DRM_RND_STATE_INITIALIZER(seed__) + +unsigned int *drm_random_order(unsigned int count, + struct rnd_state *state); +void drm_random_reorder(unsigned int *order, + unsigned int count, + struct rnd_state *state); + +#endif /* !__DRM_RANDOM_H__ */