Re: [RFC] [PATCH v5 0/3] fadvise: support POSIX_FADV_NOREUSE

[Andrea Righi <andrea@betterlinux.com>]

On Sun, Feb 12, 2012 at 11:24:27PM +0530, Aneesh Kumar K.V wrote:
> On Sun, 12 Feb 2012 12:58:34 +0100, Andrea Righi <andrea@betterlinux.com> wrote:
> > On Sun, Feb 12, 2012 at 03:16:07PM +0800, Hillf Danton wrote:
> > > Hello Andrea
> > > 
> > > On Sun, Feb 12, 2012 at 8:21 AM, Andrea Righi <andrea@betterlinux.com> wrote:
> > > [...]
> > > >  - Some of the routines to implement the generic interval tree has been taken
> > > >   from the x86 PAT code, that uses interval trees to keep track of PAT ranges
> > > >   (in the future it would be interesting to convert also the x86 PAT code to
> > > >   use the generic interval tree implementation).
> > > >
> > > Perhaps the tree implemented in this work could also be used in tracking
> > > regions in mm/hugetlb.c.
> > > 
> > > Thanks
> > > Hillf
> > 
> > Thanks, Hillf.
> > 
> > Yes, I quickly looked at the hugtlb code, it seems another potential
> > user of the interval tree. Now all the hugetlb regions are stored in a
> > list, the interval tree is a more efficient structure for lookups -
> > O(log(n)), so there are probably advantages in presence of many
> > different disjoint intervals.
> > 
> > mmh... at the moment there's not a way to map region_count() with the
> > current kinterval API, but we can easily extend it to provide also this
> > feature (count the overlap size of two intervals).
> > 
> 
> I am also extending the hugetlb region list in the hugetlb cgroup
> patchset i recently posted to make sure we don't merge region if the
> associated private data doesn't match (in my case it is the pointer to
> hugetlb cgroup). Ref:
> http://article.gmane.org/gmane.linux.kernel.mm/73829
> 
> The goal is to make sure a region add with different private value
> results in below.
> 
> 
>     old
>       |       hcg1      |
>       -------------------
> 
> new
> |             hcg2               |
> ----------------------------------
> 
> results in 
> 
>  | hcg2   | |     hcg1       | |   hcg2 |
>  ---------  __________________ ----------
> 
> 
> -aneesh

Yep! This is different from my case, at least according to the current
implementation. Using kintervals the new range hcg2 will completely
overwrite hcg1, because the default behavior is that new ranges
overwrite old ranges.

To get the same result the new range (hcg2) should be defined inside
the old range (hcg1):

     new
       |       hcg2      |
       -------------------

 old
 |             hcg1               |
 ----------------------------------

In this case result will be:

  | hcg1   | |     hcg2       | |   hcg1 |
  ---------  __________________ ----------

mmmh.. I'm wondering if there's a better way to make the intervals even
more generic, so that it would be possible to specify also a different
behavior in case of conflicts... (i.e., new wins vs old wins).

Thanks,
-Andrea