From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34965) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YfWd9-0000II-Ku for qemu-devel@nongnu.org; Tue, 07 Apr 2015 12:45:41 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YfWd8-0000jZ-H2 for qemu-devel@nongnu.org; Tue, 07 Apr 2015 12:45:39 -0400 Message-ID: <552409AA.1040101@redhat.com> Date: Tue, 07 Apr 2015 12:45:30 -0400 From: John Snow MIME-Version: 1.0 References: <1426879023-18151-1-git-send-email-jsnow@redhat.com> <1426879023-18151-16-git-send-email-jsnow@redhat.com> <20150402133724.GJ25244@stefanha-thinkpad.redhat.com> <551D6707.20501@redhat.com> <20150407125742.GA21559@stefanha-thinkpad.redhat.com> In-Reply-To: <20150407125742.GA21559@stefanha-thinkpad.redhat.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [Qemu-block] [PATCH v4 15/20] block: Resize bitmaps on bdrv_truncate List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Stefan Hajnoczi Cc: famz@redhat.com, qemu-block@nongnu.org, Stefan Hajnoczi , qemu-devel@nongnu.org, armbru@redhat.com, vsementsov@parallels.com, mreitz@redhat.com On 04/07/2015 08:57 AM, Stefan Hajnoczi wrote: > On Thu, Apr 02, 2015 at 11:57:59AM -0400, John Snow wrote: >> >> >> On 04/02/2015 09:37 AM, Stefan Hajnoczi wrote: >>> On Fri, Mar 20, 2015 at 03:16:58PM -0400, John Snow wrote: >>>> +void hbitmap_truncate(HBitmap *hb, uint64_t size) >>>> +{ >>>> + bool shrink; >>>> + unsigned i; >>>> + uint64_t num_elements = size; >>>> + uint64_t old; >>>> + >>>> + /* Size comes in as logical elements, adjust for granularity. */ >>>> + size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity; >>>> + assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); >>>> + shrink = size < hb->size; >>>> + >>>> + /* bit sizes are identical; nothing to do. */ >>>> + if (size == hb->size) { >>>> + return; >>>> + } >>>> + >>>> + /* If we're losing bits, let's clear those bits before we invalidate all of >>>> + * our invariants. This helps keep the bitcount consistent, and will prevent >>>> + * us from carrying around garbage bits beyond the end of the map. >>>> + * >>>> + * Because clearing bits past the end of map might reset bits we care about >>>> + * within the array, record the current value of the last bit we're keeping. >>>> + */ >>>> + if (shrink) { >>>> + bool set = hbitmap_get(hb, num_elements - 1); >>>> + uint64_t fix_count = (hb->size << hb->granularity) - num_elements; >>>> + >>>> + assert(fix_count); >>>> + hbitmap_reset(hb, num_elements, fix_count); >>>> + if (set) { >>>> + hbitmap_set(hb, num_elements - 1, 1); >>>> + } >>> >>> Why is it necessary to set the last bit (if it was set)? The comment >>> isn't clear to me. >>> >> >> Sure. The granularity of the bitmap provides us with virtual bit groups. for >> a granularity of say g=2, we have 2^2 virtual bits per every real bit: >> >> 101 in memory is treated, virtually, as 1111 0000 1111. >> >> The get/set calls operate on virtual bits, not concrete ones, so if we were >> to reset virtual bits 2-11: >> 11|11 0000 1111 >> >> We'd set the real bits to '000', because we clear or set the entire virtual >> group. >> >> This is probably not what we really want, so as a shortcut I just read and >> then re-set the final bit. >> >> It is programmatically avoidable (Are we truncating into a granularity >> group?) but in the case that we are, I'd need to read/reset the bit anyway, >> so it seemed fine to just unconditionally apply the fix. > > I see. This is equivalent to: > > uint64_t start = QEMU_ALIGN_UP(num_elements, hb->granularity); Probably you mean QEMU_ALIGN_UP(num_elements, 1 << hb->granularity) > uint64_t fix_count = (hb->size << hb->granularity) - start; > hbitmap_reset(hb, start, fix_count); > > The explicit QEMU_ALIGN_UP(num_elements, hb->granularity) calculation > shows that we're working around the granularity. I find this easier to > understand. > > If you keep the get/set version, please extend the comment to explain > that clearing the first bit could destroy up to granularity - 1 bits > that must be preserved. > Your solution will read more nicely, so I'll just adopt that, thanks. > Stefan >