From patchwork Tue Jan 22 21:18:51 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alasdair G Kergon X-Patchwork-Id: 2020761 Return-Path: X-Original-To: patchwork-dm-devel@patchwork.kernel.org Delivered-To: patchwork-process-083081@patchwork1.kernel.org Received: from mx3-phx2.redhat.com (mx3-phx2.redhat.com [209.132.183.24]) by patchwork1.kernel.org (Postfix) with ESMTP id D3F433FCDE for ; Tue, 22 Jan 2013 21:23:13 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by mx3-phx2.redhat.com (8.13.8/8.13.8) with ESMTP id r0MLIshC021986; Tue, 22 Jan 2013 16:18:57 -0500 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id r0MLIr61001302 for ; Tue, 22 Jan 2013 16:18:53 -0500 Received: from agk-dp.fab.redhat.com (agk-dp.fab.redhat.com [10.33.0.20]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r0MLIpJf023777 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 22 Jan 2013 16:18:52 -0500 Received: from agk by agk-dp.fab.redhat.com with local (Exim 4.69) (envelope-from ) id 1TxlF5-0007wS-HT; Tue, 22 Jan 2013 21:18:51 +0000 Date: Tue, 22 Jan 2013 21:18:51 +0000 From: Alasdair G Kergon To: Joe Thornber Message-ID: <20130122211851.GB30267@agk-dp.fab.redhat.com> Mail-Followup-To: Joe Thornber , dm-devel@redhat.com References: <1355429956-22785-1-git-send-email-ejt@redhat.com> <1355429956-22785-7-git-send-email-ejt@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <1355429956-22785-7-git-send-email-ejt@redhat.com> Organization: Red Hat UK Ltd. Registered in England and Wales, number 03798903. Registered Office: 64 Baker Street, 4th floor, London, W1U 7DF. User-Agent: Mutt/1.5.18 (2008-05-17) X-Scanned-By: MIMEDefang 2.68 on 10.5.11.23 X-loop: dm-devel@redhat.com Cc: dm-devel@redhat.com Subject: Re: [dm-devel] [PATCH 6/8] [persistent-data] Add a transactional array. X-BeenThere: dm-devel@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk Reply-To: device-mapper development List-Id: device-mapper development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: dm-devel-bounces@redhat.com Errors-To: dm-devel-bounces@redhat.com Reading first only the interface file (all-caches version), I'm left with the following questions about how to use the interface: please would you try to update the comments so they answer the questions? Thanks, Alasdair +/* + * Lookup a value in the array + * + * info - describes the array + * root - root block of the array + * index - array index + * value - the value to be read. Will be in on disk format of course. + * + * -ENODATA will be returned if the index is out of bounds. + */ +int dm_array_get(struct dm_array_info *info, dm_block_t root, + uint32_t index, void *value); Is this like dm_get() ? In what sense does dm_array_get get a dm_array? - get_value? lookup? +/* + * Set an entry in the array. + * + * info - describes the array + * root - root block of the array + * index - array index + * value - value to be written to disk. Make sure you bless this before + * calling. How do I 'bless this'? Must 'value' conform to the definition in info->value_type? + * new_root - the new root block + * + * The old value being overwritten will be decremented, the new value + * incremented. + * + * -ENODATA will be returned if the index is out of bounds. + */ +int dm_array_set(struct dm_array_info *info, dm_block_t root, + uint32_t index, const void *value, dm_block_t *new_root) + __dm_written_to_disk(value); Define dm_array_set before dm_array_get in this file, perhaps? set_value? store? rather then implying it's setting the whole array? What am I supposed to do with 'new_root'? Does 'root' become invalid? Perhaps a general comment at the top about root and new_root would be a good way to explain. +/* + * Walk through all the entries in an array. + * + * info - describes the array + * root - root block of the array + * fn - called back for every element + * context - passed to the callback + */ +int dm_array_walk(struct dm_array_info *info, dm_block_t root, + int (*fn)(void *, uint64_t key, void *leaf), Make that 'void *context' so it's more obvious where it comes from? + void *context); + +/*----------------------------------------------------------------*/ + +#endif --- dm-devel mailing list dm-devel@redhat.com https://www.redhat.com/mailman/listinfo/dm-devel --- /dev/null +++ linux/drivers/md/persistent-data/dm-array.h @@ -0,0 +1,128 @@ +/* + * Copyright (C) 2012 Red Hat, Inc. + * + * This file is released under the GPL. + */ +#ifndef _LINUX_DM_ARRAY_H +#define _LINUX_DM_ARRAY_H + +#include "dm-btree.h" + +/*----------------------------------------------------------------*/ + +/* + * The dm-array is a persistent version of an array. It packs the data What sort of array? + * more efficiently than a btree which will result in less disk space use, + * and a performance boost. The get and set operations are still O(ln(n)), + * but with a much smaller constant. + * + * The value type structure is reused from the btree type to support proper + * reference counting of values. + * + * The arrays implicitly know their length, and bounds are checked for + * lookups and updates. It doesn't store this in an accessible place + * because it would waste a whole metadata block. Make sure you store the + * size along with the array root in your encompassing data. + */ How are array entries indexed? Consecutive integers? Starting from 0 or 1? Or can arrays be sparse, with the 'size' being the number of populated entries? +/* + * Describes an array. Don't initialise this structure yourself, use the + * setup function below. + */ +struct dm_array_info { + struct dm_transaction_manager *tm; + struct dm_btree_value_type value_type; + struct dm_btree_info btree_info; +}; What is the normal way to initialise an array of a specific size (that it says the caller must track)? What error do I get if I try to add an element that would take it beyond the size the array is defined to have? +/* + * Sets up a dm_array_info structure. + * + * info - the structure being filled in. + * tm - the transaction manager that should supervise this structure. + * vt - describes the leaf values. + */ +void dm_setup_array_info(struct dm_array_info *info, + struct dm_transaction_manager *tm, + struct dm_btree_value_type *vt); + +/* + * Initialise an empty array, zero length array. + * + * info - describes the array Must this be populated first by calling dm_array_info() ? + * root - on success this will be filled out with the root block And must this root block then be passed into all the functions that manipulate the array? The description of dm_btree_empty() in dm-btree.h is that that function does 'Set up' and it's clearly paired with dm_btree_del(). Is there a counterpart to dm_setup_array_info if I want to destroy it or isn't one needed? Is this similar to what dm_bitset_info_init() is doing and would an _init suffix instead of 'setup' be clearer here too? + */ +int dm_array_empty(struct dm_array_info *info, dm_block_t *root); Is it compulsory to call this function after calling dm_setup_array_info()? [Otherwise I wouldn't have a 'root' I can use?] But if so, how do I set the actual length of the array I want to use (which it says I must keep track myself)? Am I required also to call dm_array_resize() afterwards with an old_size of 0 because an array with a size of 0 would otherwise be useless to me? If I call this on an existing populated array will it 'empty' it correctly like the name suggests or shouldn't that be done? +/* + * Resizes the array. + * + * info - describes the array + * root - the root block of the array on disk + * old_size - yes, the caller is responsible for remembering the size of the array + * new_size - can be bigger or smaller than old_size + * value - if we're growing the array the new entries will have this value + * new_root - on success, points to the new root block + * + * If growing the inc function for value will be called the appropriate + * number of times. So if the caller is holding a reference they may want + * to drop it. + */ +int dm_array_resize(struct dm_array_info *info, dm_block_t root, + uint32_t old_size, uint32_t new_size, + const void *value, dm_block_t *new_root) + __dm_written_to_disk(value); If it gives me 'new_root' does that mean I must replace my copy of 'root' with it and does the old 'root' remain valid in any way or not? +/* + * Frees a whole array. The value_type's decrement operation will be called + * for all values in the array + */ +int dm_array_del(struct dm_array_info *info, dm_block_t root); Does anything remain valid after calling this? - Is root no longer valid? - Without touching 'info', can I call dm_array_empty() again at this point?