From mboxrd@z Thu Jan 1 00:00:00 1970 From: =?ISO-8859-1?Q?Christian_K=F6nig?= Subject: Re: [PATCH 09/26] drm/radeon: add biggest hole tracking and wakequeue to the sa v3 Date: Tue, 01 May 2012 14:22:51 +0200 Message-ID: <4F9FD59B.1050404@vodafone.de> References: <1335797464-14317-1-git-send-email-deathsimple@vodafone.de> <1335797464-14317-10-git-send-email-deathsimple@vodafone.de> Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; Format="flowed" Content-Transfer-Encoding: quoted-printable Return-path: Received: from outgoing.email.vodafone.de (outgoing.email.vodafone.de [139.7.28.128]) by gabe.freedesktop.org (Postfix) with ESMTP id 40ADC9E759 for ; Tue, 1 May 2012 05:22:55 -0700 (PDT) In-Reply-To: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: dri-devel-bounces+sf-dri-devel=m.gmane.org@lists.freedesktop.org Errors-To: dri-devel-bounces+sf-dri-devel=m.gmane.org@lists.freedesktop.org To: Jerome Glisse Cc: airlied@redhat.com, dri-devel@lists.freedesktop.org List-Id: dri-devel@lists.freedesktop.org On 30.04.2012 17:45, Jerome Glisse wrote: > On Mon, Apr 30, 2012 at 10:50 AM, Christian K=F6nig > wrote: >> With that in place clients are automatically blocking >> until their memory request can be handled. >> >> v2: block only if the memory request can't be satisfied >> in the first try, the first version actually lacked >> a night of sleep. >> >> v3: make blocking optional, update comments and fix >> another bug with biggest hole tracking. >> >> Signed-off-by: Christian K=F6nig > I would say NAK, the idea of SA allocator is to be like ring buffer, a > ring allocation. All the allocation made through SA are made for > object that life are ring related, ie once allocated the object is > scheduled through one of the ring and once the ring is done consuming > it the object is free. So the idea behind the SA allocator is to make > it simple we keep track of the highest offset used and the lowest one > free, we try to find room above the highest and if we don't have > enough room we try at the begining of the ring (wrap over), idea is > that in most scenario we don't have to wait because SA is big enough > and if we have to wait well it's because GPU is full of things to do > so waiting a bit won't starve the GPU. Take a closer look, that's exactly what the new code intends to do. The biggest_hole is tracking the bottom of the ring allocation algorithm: In (roughly estimated) 97% of all cases it is pointing after the last = allocation, so new allocations can be directly served. In 1% of the cases it is pointing to a free block at the end of the = buffer that isn't big enough to serve the next allocation, in that case = we just need to make one step to the beginning of the buffer and = (assuming that allocations are ring like) there should be enough space = gathered to serve the allocation. In 1% of the cases a left over allocation will prevent a new = biggest_hole to gather together at the beginning of the buffer, but that = is actually unproblematic, cause all that needs to be done is stepping = over that unreleased chunk of memory. And well every algorithm has a worst case and here it happens when there = isn't enough room to server the allocation, in this case we need to do a = full cycle around all allocations and then optionally wait for the = biggest_hole to increase in size. > That being said current code doesn't exactly reflect that, i can't > remember why. Anyway i would rather make current looks like intented > as i believe it make allocation easy and fast in usual case. There is > also a reason why i intended to have several sa manager. Idea is to > have one SA manager for the VM (because VM might last longer) and one > for all the ring object (semaphore, ib, ...) because usual case is > that all ring sync from time to time and the all progress in //. Yeah, even with your good intentions the current code just turned out to = be a linear search over all the allocations and that seemed to be not so = efficient. Also making the code look like it should from the comments = description was also part of my intentions. Anyway, I think it's definitely an improvement, but there obviously is = also still room for new ideas, e.g. we could track how trustworthy the = biggest_hole is and then early abort allocations that can never succeed. = Or we could also keep track of the last allocation and on new = allocations try once to place them directly behind the last allocation = first, that would give the whole allocator a even more ring like fashion. And by the way: Having two allocators, one for VM and another for the = ring like stuff sounds like the right thing to do, since their = allocations seems to have different live cycles. Christian.