# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
# ChangeSet 1.808 -> 1.809
# include/linux/kernel.h 1.24 -> 1.25
# lib/Makefile 1.14 -> 1.15
# (new) -> 1.1 lib/bsearch.c
# (new) -> 1.1 lib/qsort.c
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/10/21 [email protected] 1.809
# Add generic qsort() and bsearch(): qsort() from BSD, bsearch() from glibc
# --------------------------------------------
#
diff -Nru a/include/linux/kernel.h b/include/linux/kernel.h
--- a/include/linux/kernel.h Mon Oct 21 17:14:38 2002
+++ b/include/linux/kernel.h Mon Oct 21 17:14:38 2002
@@ -215,4 +215,9 @@
#define __FUNCTION__ (__func__)
#endif
+void qsort(void *base, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *));
+void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *));
+
#endif
diff -Nru a/lib/Makefile b/lib/Makefile
--- a/lib/Makefile Mon Oct 21 17:14:38 2002
+++ b/lib/Makefile Mon Oct 21 17:14:38 2002
@@ -9,10 +9,11 @@
L_TARGET := lib.a
export-objs := cmdline.o dec_and_lock.o rwsem-spinlock.o rwsem.o \
- crc32.o rbtree.o radix-tree.o
+ crc32.o rbtree.o radix-tree.o qsort.o bsearch.o
obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o \
- bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o
+ bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
+ qsort.o bsearch.o
obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff -Nru a/lib/bsearch.c b/lib/bsearch.c
--- /dev/null Wed Dec 31 16:00:00 1969
+++ b/lib/bsearch.c Mon Oct 21 17:14:38 2002
@@ -0,0 +1,49 @@
+/* Copyright (C) 1991, 1992, 1997, 2000 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public
+ License along with the GNU C Library; see the file COPYING.LIB. If not,
+ write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+
+/* Perform a binary search for KEY in BASE which has NMEMB elements
+ of SIZE bytes each. The comparisons are done by (*COMPAR)(). */
+void *
+bsearch(const void *key, const void *base, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *))
+{
+ size_t l, u, idx;
+ const void *p;
+ int comparison;
+
+ l = 0;
+ u = nmemb;
+ while (l < u) {
+ idx = (l + u) / 2;
+ p = (void *)(((const char *)base) + (idx * size));
+ comparison = (*compar)(key, p);
+ if (comparison < 0)
+ u = idx;
+ else if (comparison > 0)
+ l = idx + 1;
+ else
+ return (void *)p;
+ }
+
+ return NULL;
+}
+
+EXPORT_SYMBOL(bsearch);
diff -Nru a/lib/qsort.c b/lib/qsort.c
--- /dev/null Wed Dec 31 16:00:00 1969
+++ b/lib/qsort.c Mon Oct 21 17:14:38 2002
@@ -0,0 +1,180 @@
+/*
+ * Update: The Berkeley copyright was changed, and the change
+ * is retroactive to all "true" BSD software (ie everything
+ * from UCB as opposed to other peoples code that just carried
+ * the same license). The new copyright doesn't clash with the
+ * GPL, so the module-only restriction has been removed..
+ */
+
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ * Copyright (c) 2002 SGI
+ * Copyright (c) 2002 Sun Microsystems, Inc.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * From:
+ * @(#)qsort.c 8.1 (Berkeley) 6/4/93
+ * FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.11 2002/03/22 21:53:10
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+
+typedef int cmp_t(const void *, const void *);
+static inline char *med3(char *, char *, char *, cmp_t *);
+static inline void swapfunc(char *, char *, int, int);
+
+/*
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ */
+#define swapcode(TYPE, parmi, parmj, n) do { \
+ long i = (n) / sizeof (TYPE); \
+ TYPE *pi = (TYPE *) (parmi); \
+ TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+} while (0)
+
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static inline void
+swapfunc(char *a, char *b, int n, int swaptype)
+{
+ if(swaptype <= 1)
+ swapcode(long, a, b, n);
+ else
+ swapcode(char, a, b, n);
+}
+
+#define swap(a, b) do { \
+ if (swaptype == 0) { \
+ long t = *(long *)(a); \
+ *(long *)(a) = *(long *)(b); \
+ *(long *)(b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype); \
+} while (0)
+
+#define vecswap(a, b, n) do { \
+ if ((n) > 0) swapfunc(a, b, n, swaptype); \
+} while (0)
+
+static inline char *
+med3(char *a, char *b, char *c, cmp_t *cmp)
+{
+ return cmp(a, b) < 0 ?
+ (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
+ :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+}
+
+void
+qsort(void *a, size_t n, size_t es, cmp_t *cmp)
+{
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ int d, r, swaptype, swap_cnt;
+
+loop: SWAPINIT(a, es);
+ swap_cnt = 0;
+ if (n < 7) {
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+ pm = (char *)a + (n / 2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = (char *)a + (n - 1) * es;
+ if (n > 40) {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp);
+ pm = med3(pm - d, pm, pm + d, cmp);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp);
+ }
+ pm = med3(pl, pm, pn, cmp);
+ }
+ swap(a, pm);
+ pa = pb = (char *)a + es;
+
+ pc = pd = (char *)a + (n - 1) * es;
+ for (;;) {
+ while (pb <= pc && (r = cmp(pb, a)) <= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (r = cmp(pc, a)) >= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ swap_cnt = 1;
+ pb += es;
+ pc -= es;
+ }
+ if (swap_cnt == 0) { /* Switch to insertion sort */
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+
+ pn = (char *)a + n * es;
+ r = min_t(long, pa - (char *)a, pb - pa);
+ vecswap(a, pb - r, r);
+ r = min_t(long, pd - pc, pn - pd - es);
+ vecswap(pb, pn - r, r);
+ if ((r = pb - pa) > es)
+ qsort(a, r / es, es, cmp);
+ if ((r = pd - pc) > es) {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
+}
+
+EXPORT_SYMBOL(qsort);
On Mon, Oct 21, 2002 at 05:36:25PM -0700, Timothy Hockin wrote:
> + * 3. All advertising materials mentioning features or use of this software
> + * must display the following acknowledgement:
> + * This product includes software developed by the University of
> + * California, Berkeley and its contributors.
Ahem.
Since the copyright holder appears to be the Regents of the University
of California, you have permission to remove this
(ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change).
Also, you must remove this clause for the code to be suitable for
inclusion in Linux. Not only is the advertising clause incompatible
with the GPL, but imagine what a pain it would be to include this
acknowedgement in any sort of advertisement. If you think I'm
overreacting, check out this lovely cruft from NetBSD's INSTALL
document:
This product includes software developed by the University of California,
Berkeley and its contributors.
This product includes software developed by The NetBSD Foundation, Inc.
This product includes software developed by the NetBSD Foundation,
Inc. and its contributors.
This product includes software developed by the Computer Systems Engi-
neering Group at Lawrence Berkeley Laboratory.
This product includes software developed by Adam Glass and Charles Han-
num.
This product includes software developed by Adam Glass and Charles M.
Hannum.
This product includes software developed by Adam Glass.
This product includes software developed by Alistair G. Crooks.
This product includes software developed by Amancio Hasty and Roger
Hardiman.
This product includes software developed by Berkeley Software Design,
Inc.
This product includes software developed by Bill Paul.
This product includes software developed by Charles D. Cranor and Wash-
ington University.
This product includes software developed by Charles D. Cranor.
This product includes software developed by Charles Hannum, by the Uni-
versity of Vermont and State Agricultural College and Garrett A. Wollman,
by William F. Jolitz, and by the University of California, Berkeley,
Lawrence Berkeley Laboratory, and its contributors.
This product includes software developed by Charles Hannum.
This product includes software developed by Charles M. Hannum.
This product includes software developed by Chris Provenzano.
This product includes software developed by Christian E. Hopps.
This product includes software developed by Christopher G. Demetriou for
the NetBSD Project.
This product includes software developed by Christopher G. Demetriou.
This product includes software developed by Christos Zoulas.
This product includes software developed by David Jones and Gordon Ross.
This product includes software developed by Dean Huxley.
This product includes software developed by Eric S. Hvozda.
This product includes software developed by Ezra Story.
This product includes software developed by Gardner Buchanan.
This product includes software developed by Gordon Ross.
This product includes software developed by Gordon W. Ross and Leo Wep-
pelman.
This product includes software developed by Gordon W. Ross.
This product includes software developed by Hauke Fath.
This product includes software developed by HAYAKAWA Koichi.
This product includes software developed by Hellmuth Michaelis and Joerg
Wunsch.
This product includes software developed by Herb Peyerl.
This product includes software developed by Holger Veit and Brian Moore
for use with "386BSD" and similar operating systems.
This product includes software developed by Hubert Feyrer for the NetBSD
Project.
This product includes software developed by Iain Hibbert.
This product includes software developed by Ian W. Dall.
This product includes software developed by Ignatios Souvatzis for the
NetBSD Project.
This product includes software developed by Jason R. Thorpe for And Com-
munications, http://www.and.com/.
This product includes software developed by Joachim Koenig-Baltes.
This product includes software developed by Jochen Pohl for The NetBSD
Project.
This product includes software developed by John Polstra.
This product includes software developed by Jonathan Stone and Jason R.
Thorpe for the NetBSD Project.
This product includes software developed by Jonathan Stone for the NetBSD
Project.
This product includes software developed by Jonathan Stone.
This product includes software developed by Julian Highfield.
This product includes software developed by Kenneth Stailey.
This product includes software developed by Leo Weppelman.
This product includes software developed by Lloyd Parkes.
This product includes software developed by Manuel Bouyer.
This product includes software developed by Marc Horowitz.
This product includes software developed by Mark Brinicombe for the NetB-
SD Project.
This product includes software developed by Mark Brinicombe.
This product includes software developed by Mark Tinguely and Jim Lowe.
This product includes software developed by Markus Wild.
This product includes software developed by Martin Husemann and Wolfgang
Solfrank.
This product includes software developed by Mats O Jansson and Charles D.
Cranor.
This product includes software developed by Mats O Jansson.
This product includes software developed by Matthias Pfaller.
This product includes software developed by Michael L. Hitch.
This product includes software developed by Niels Provos.
This product includes software developed by Paul Kranenburg.
This product includes software developed by Paul Mackerras.
This product includes software developed by Peter Galbavy.
This product includes software developed by Philip A. Nelson.
This product includes software developed by Rodney W. Grimes.
This product includes software developed by Roland C. Dowdeswell.
This product includes software developed by Rolf Grossmann.
This product includes software developed by Scott Bartram.
This product includes software developed by SigmaSoft, Th. Lockert.
This product includes software developed by Tatoku Ogaito for the NetBSD
Project.
This product includes software developed by Terrence R. Lambert.
This product includes software developed by Theo de Raadt and John
Brezak.
This product includes software developed by Theo de Raadt.
This product includes software developed by Tohru Nishimura for the NetB-
SD Project.
This product includes software developed by TooLs GmbH.
This product includes software designed by William Allen Simpson.
This product includes software developed by Winning Strategies, Inc.
This product includes software developed by Zembu Labs, Inc.
This product includes software developed by the Center for Software Sci-
ence at the University of Utah.
This product includes software developed by the Computer Systems Labora-
tory at the University of Utah.
This product includes software developed by the University of Calgary De-
partment of Computer Science and its contributors.
This product includes software developed by the University of Vermont and
State Agricultural College and Garrett A. Wollman.
This product includes software developed for the FreeBSD project.
This product includes software developed for the Internet Software Con-
sortium by Ted Lemon.
This product includes software developed for the NetBSD Project by Frank
van der Linden.
This product includes software developed for the NetBSD Project by Jason
R. Thorpe.
This product includes software developed for the NetBSD Project by John
M. Vinopal.
This product includes software developed for the NetBSD Project by
Matthias Drochner.
This product includes software developed for the NetBSD Project by
Matthieu Herrb.
This product includes software developed for the NetBSD Project by Perry
E. Metzger.
This product includes software developed for the NetBSD Project by Pier-
mont Information Systems Inc.
This product includes software developed for the NetBSD Project by Ted
Lemon.
This product includes software developed for the NetBSD Project by Wasabi
Systems, Inc.
This product includes software developed by LAN Media Corporation and its
contributors.
This product includes software developed by Michael Graff for the NetBSD
Project.
This product includes software developed by Niklas Hallqvist, C Stone and
Job de Haas.
This product includes software developed by Eric Young (eay@min-
com.oz.au).
This product includes software developed by the OpenSSL Project for use
in the OpenSSL Toolkit (http://www.openssl.org/).
This product includes software developed by the University of Oregon.
This product includes software developed by the University of Southern
California and/or Information Sciences Institute.
This product includes software developed by Internet Initiative Japan
Inc.
This product includes software developed by Reinoud Zandijk.
This product includes software developed at the Information Technology
Division, US Naval Research Laboratory.
In the following statement, "This software" refers to the Mitsumi CD-ROM
driver:
This software was developed by Holger Veit and Brian Moore for use
with "386BSD" and similar operating systems. "Similar operating
systems" includes mainly non-profit oriented systems for research
and education, including but not restricted to "NetBSD" , "FreeBSD"
, "Mach" (by CMU).
In the following statement, "This software" refers to the parallel port
driver:
This software is a component of "386BSD" developed by William F.
Jolitz, TeleMuse.
Ok sanity check time. Why do you need qsort and bsearch for this kind of
thing. Just how many groups do you plan to support ?
On Tue, 2002-10-22 at 18:26, Tim Hockin wrote:
> Alan Cox wrote:
> > Ok sanity check time. Why do you need qsort and bsearch for this kind of
> > thing. Just how many groups do you plan to support ?
>
> Unlimited - we've tested with tens of thousands.
Now how about the real world requirements ?
Alan Cox wrote:
> Ok sanity check time. Why do you need qsort and bsearch for this kind of
> thing. Just how many groups do you plan to support ?
Unlimited - we've tested with tens of thousands.
--
Tim Hockin
Systems Software Engineer
Sun Microsystems, Linux Kernel Engineering
[email protected]
Alan Cox wrote:
> On Tue, 2002-10-22 at 18:26, Tim Hockin wrote:
>
>>Alan Cox wrote:
>>
>>>Ok sanity check time. Why do you need qsort and bsearch for this kind of
>>>thing. Just how many groups do you plan to support ?
>>
>>Unlimited - we've tested with tens of thousands.
>
>
> Now how about the real world requirements ?
Those were real world requirements - we got the number 10,000 from our
product management, which (presumably) spoke with customers. On the
hosting systems, it is really possible to have thousands of virtual sites.
Now, I don't much care if you want it to be a linear search, and I'll
revert it, if needed, but qsort() is already in in XFS specific code,
and bsearch is small. It doesn't negatively impact any fast path, and
provides better behavior for the crazies that really want 10,000 groups.
Tim
--
Tim Hockin
Systems Software Engineer
Sun Microsystems, Linux Kernel Engineering
[email protected]
Aaron Lehmann wrote:
> On Mon, Oct 21, 2002 at 05:36:25PM -0700, Timothy Hockin wrote:
>
>>+ * 3. All advertising materials mentioning features or use of this software
>>+ * must display the following acknowledgement:
>>+ * This product includes software developed by the University of
>>+ * California, Berkeley and its contributors.
>
>
> Ahem.
>
> Since the copyright holder appears to be the Regents of the University
> of California, you have permission to remove this
> (ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change).
Done, in BK at the same URL. Thanks for the reference.
--
Tim Hockin
Systems Software Engineer
Sun Microsystems, Linux Kernel Engineering
[email protected]
On Tuesday 22 October 2002 12:37 pm, Tim Hockin wrote:
> Alan Cox wrote:
> > On Tue, 2002-10-22 at 18:26, Tim Hockin wrote:
> >>Alan Cox wrote:
> >>>Ok sanity check time. Why do you need qsort and bsearch for this kind of
> >>>thing. Just how many groups do you plan to support ?
> >>
> >>Unlimited - we've tested with tens of thousands.
> >
> > Now how about the real world requirements ?
>
> Those were real world requirements - we got the number 10,000 from our
> product management, which (presumably) spoke with customers. On the
> hosting systems, it is really possible to have thousands of virtual sites.
>
> Now, I don't much care if you want it to be a linear search, and I'll
> revert it, if needed, but qsort() is already in in XFS specific code,
> and bsearch is small. It doesn't negatively impact any fast path, and
> provides better behavior for the crazies that really want 10,000 groups.
>
> Tim
Does it actually work with NFS???? or any networked file system?
Most of them limit ngroups to 16 to 32, and cannot send any data
if there is an overflow, since that overflow would replace all of the
data you try to send/recieve...
And I really doubt that anybody has 10000 unique groups (or even
close to that) running under any system. The center I'm at has
some of the largest UNIX systems ever made, and there are only
about 600 unique groups over the entire center. The largest number
of groups a user can be in is 32. And nobody even comes close.
--
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
Jesse Pollard wrote:
> Does it actually work with NFS???? or any networked file system?
> Most of them limit ngroups to 16 to 32, and cannot send any data
> if there is an overflow, since that overflow would replace all of the
> data you try to send/recieve...
NFS has a smaller limit, that is correct. An unfortunate limitation.
> And I really doubt that anybody has 10000 unique groups (or even
> close to that) running under any system. The center I'm at has
> some of the largest UNIX systems ever made, and there are only
> about 600 unique groups over the entire center. The largest number
> of groups a user can be in is 32. And nobody even comes close.
I'm glad it doesn't affect you. If it was a more common problem, it
would have been solved a long time ago. It does affect some people,
though. Maybe they can redesign their group structures, but why not
remove this arbitrary limit, since we can?
Tim
--
Tim Hockin
Systems Software Engineer
Sun Microsystems, Linux Kernel Engineering
[email protected]
On Tue, 22 Oct 2002, Tim Hockin wrote:
> Jesse Pollard wrote:
>
> > And I really doubt that anybody has 10000 unique groups (or even
> > close to that) running under any system. The center I'm at has
> > some of the largest UNIX systems ever made, and there are only
> > about 600 unique groups over the entire center. The largest number
> > of groups a user can be in is 32. And nobody even comes close.
>
> I'm glad it doesn't affect you. If it was a more common problem, it
> would have been solved a long time ago. It does affect some people,
> though. Maybe they can redesign their group structures, but why not
> remove this arbitrary limit, since we can?
For anoncvs this is a common problem.
Each project has its own group and the anoncvs user needs
access to all (write access in order to make lock files).
regards,
Rik
--
A: No.
Q: Should I include quotations after my reply?
http://www.surriel.com/ http://distro.conectiva.com/
On Tuesday 22 October 2002 01:21 pm, Tim Hockin wrote:
> Jesse Pollard wrote:
> > Does it actually work with NFS???? or any networked file system?
> > Most of them limit ngroups to 16 to 32, and cannot send any data
> > if there is an overflow, since that overflow would replace all of the
> > data you try to send/recieve...
>
> NFS has a smaller limit, that is correct. An unfortunate limitation.
>
> > And I really doubt that anybody has 10000 unique groups (or even
> > close to that) running under any system. The center I'm at has
> > some of the largest UNIX systems ever made, and there are only
> > about 600 unique groups over the entire center. The largest number
> > of groups a user can be in is 32. And nobody even comes close.
>
> I'm glad it doesn't affect you. If it was a more common problem, it
> would have been solved a long time ago. It does affect some people,
> though. Maybe they can redesign their group structures, but why not
> remove this arbitrary limit, since we can?
Think about a while - if a file write (say 1K in length) must include 10000
groups (at 16 bits/group? 32bits?) then the resulting transaction becomes
1K + 2*10K -> 21K (or 1K+4*10K -> 41K). This is over 20 times the overhead.
No I don't expect the structures to be changed that much.
I am in favor of being able to change the limits, but lets be reasonable.
I can see a use for 64 groups, but not much over. Even that introduces
a practical security problem (leakage of data from one authorized group
to unauthorized groups).
By the time you get one or more people with that many groups you
may as well put everybody in one group and be done with it.
ACLs would be much more usefull, and controllable than 10000 groups
anyway. At least the owner of the file would be able to specify exactly
what access is being granted, and to whom.
BTW, a bsearch algorithm is slow compaired to a radix search in
sparse trees...
--
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
On Tue, 22 Oct 2002, Jesse Pollard wrote:
> I am in favor of being able to change the limits, but lets be reasonable.
> I can see a use for 64 groups, but not much over.
Anoncvs.
Rik
--
A: No.
Q: Should I include quotations after my reply?
http://www.surriel.com/ http://distro.conectiva.com/
On Tue, Oct 22, 2002 at 01:03:47PM -0500, Jesse Pollard wrote:
>
> And I really doubt that anybody has 10000 unique groups (or even
> close to that) running under any system. The center I'm at has
> some of the largest UNIX systems ever made, and there are only
> about 600 unique groups over the entire center. The largest number
> of groups a user can be in is 32. And nobody even comes close.
Large CVS hosting operations like GNU Savannah have historically used
patches to increase NGROUPS. Using one group per project in CVS is the
sanest way to manage a big repository with complex permissions.
miket
>>>>> "Jesse" == Jesse Pollard <[email protected]> writes:
Jesse> On Tuesday 22 October 2002 12:37 pm, Tim Hockin wrote:
>> Alan Cox wrote:
>> > On Tue, 2002-10-22 at 18:26, Tim Hockin wrote:
>> >>Alan Cox wrote:
>> >>>Ok sanity check time. Why do you need qsort and bsearch for this kind of
>> >>>thing. Just how many groups do you plan to support ?
>> >>
>> >>Unlimited - we've tested with tens of thousands.
>> >
>> > Now how about the real world requirements ?
>>
>> Those were real world requirements - we got the number 10,000 from our
>> product management, which (presumably) spoke with customers. On the
>> hosting systems, it is really possible to have thousands of virtual sites.
>>
>> Now, I don't much care if you want it to be a linear search, and I'll
>> revert it, if needed, but qsort() is already in in XFS specific code,
>> and bsearch is small. It doesn't negatively impact any fast path, and
>> provides better behavior for the crazies that really want 10,000 groups.
>>
>> Tim
Jesse> Does it actually work with NFS???? or any networked file
Jesse> system? Most of them limit ngroups to 16 to 32, and cannot
Jesse> send any data if there is an overflow, since that overflow
Jesse> would replace all of the data you try to send/recieve...
Jesse> And I really doubt that anybody has 10000 unique groups (or
Jesse> even close to that) running under any system. The center I'm at
Jesse> has some of the largest UNIX systems ever made, and there are
Jesse> only about 600 unique groups over the entire center. The
Jesse> largest number of groups a user can be in is 32. And nobody
Jesse> even comes close.
$ ypcat group | wc -l
9527
$ ypcat passwd | wc -l
62076
Yes, we're insane :-)
OTOH, we use AFS and PTS groups, because Unix groups don't scale. And
we would not use the ngroups mechanism in Linux even if it did,
because we need to inter-operate with Solaris.
Cheers, Hildo
On Tuesday 22 October 2002 02:45 pm, Mike Touloumtzis wrote:
> On Tue, Oct 22, 2002 at 01:03:47PM -0500, Jesse Pollard wrote:
> > And I really doubt that anybody has 10000 unique groups (or even
> > close to that) running under any system. The center I'm at has
> > some of the largest UNIX systems ever made, and there are only
> > about 600 unique groups over the entire center. The largest number
> > of groups a user can be in is 32. And nobody even comes close.
>
> Large CVS hosting operations like GNU Savannah have historically used
> patches to increase NGROUPS. Using one group per project in CVS is the
> sanest way to manage a big repository with complex permissions.
OK, I'll bite..
Why is this?
I saw the post about having to have access to a lock directory by a
cvsuser, but how is that different than having that directory with an
ACL entry that includes the cvsuser? Or an ACL that includes the
group that the cvsuser is a member of?
Granted, each project repository would have such a directory for
locks belonging to the project, but that seems to already be the
case. Setting up the ACL would just be one additional step in
setting up a project.
--
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
On Tue, Oct 22, 2002 at 03:13:41PM -0500, Jesse Pollard wrote:
> On Tuesday 22 October 2002 02:45 pm, Mike Touloumtzis wrote:
> >
> > Large CVS hosting operations like GNU Savannah have historically used
> > patches to increase NGROUPS. Using one group per project in CVS is the
> > sanest way to manage a big repository with complex permissions.
>
> OK, I'll bite..
>
> Why is this?
I only learned about this by reading the docs on Savannah; the admins can
provide better information. But my understanding is simply that they have
M users and N projects, and they want the system to support any number of
permission pairs from M x N, i.e. they want each user to be able to commit
to an arbitrary number of projects. And CVS relies on OS permissions.
> I saw the post about having to have access to a lock directory by a
> cvsuser, but how is that different than having that directory with an
> ACL entry that includes the cvsuser? Or an ACL that includes the
> group that the cvsuser is a member of?
I guess they prefer to use traditional Unix permissions rather than ACLs.
I have the same preference. Unix groups are well supported by tools and
the kind of permission setup I described above is nicely transparent
to administer. Granting a user write access to a project is simply
'adduser username projectname', and a project can easily support a large
number of writers without big ACLs.
The issue is not just lock directories, but the right to change any
file in a project, i.e. full CVS commit access to the project rather
than anonymous access. So they would need an ACL on each file in the
repository, and they would need new files to inherit ACLs from their
parent directories (I've never used ACLs on Linux but I assume this kind
of thing is supported).
miket
>>>>> "Jesse" == Jesse Pollard <[email protected]> writes:
Jesse> On Tuesday 22 October 2002 12:37 pm, Tim Hockin wrote:
Jesse> And I really doubt that anybody has 10000 unique groups (or
Jesse> even close to that) running under any system. The center I'm at
well... if you put each user in his or her own group, the total number
of unique groups gets pretty big pretty fast.
That doesn't mean, however, that one needs to be in thousands of
groups simultaneously.
Peter C
On Tue, Oct 22, 2002 at 01:03:47PM -0500, Jesse Pollard wrote:
> And I really doubt that anybody has 10000 unique groups (or even
> close to that) running under any system. The center I'm at has
> some of the largest UNIX systems ever made, and there are only
> about 600 unique groups over the entire center. The largest number
> of groups a user can be in is 32. And nobody even comes close.
It happens. We have a bunch of webservers with the web user in thousands
of groups, and we ran into the per-process limit a long, long time ago.
My solution was a bit simpler, however:
static int supplemental_group_member(gid_t grp)
{
int i = current->ngroups;
+ if (current->uid == 80)
+ if (grp >= 1000)
+ return 1;
O:)
This allows us to have a group-per-user policy where the web server has
access to each user's files without allowing any user to have access to
files belonging to any other user, which is quite useful.
Simon-
[ Simon Kirby ][ Network Operations ]
[ [email protected] ][ NetNation Communications ]
[ Opinions expressed are not necessarily those of my employer. ]
> -----Original Message-----
> From: Peter Chubb [mailto:[email protected]]
> Sent: 23 October 2002 01:09
> To: Jesse Pollard
> Cc: Tim Hockin; Linux Kernel Mailing List
> Subject: Re: [BK PATCH 1/4] fix NGROUPS hard limit (resend)
>
>
> >>>>> "Jesse" == Jesse Pollard <[email protected]> writes:
>
> Jesse> On Tuesday 22 October 2002 12:37 pm, Tim Hockin wrote:
>
> Jesse> And I really doubt that anybody has 10000 unique groups (or
> Jesse> even close to that) running under any system. The center I'm at
>
> well... if you put each user in his or her own group, the total number
> of unique groups gets pretty big pretty fast.
>
> That doesn't mean, however, that one needs to be in thousands of
> groups simultaneously.
>
> Peter C
IIRC, the RedHat distro tries to put each new user in their own
group by default.
Phil
---------------------------------------------
Phil Randal
Network Engineer
Herefordshire Council
Hereford, UK
On Tuesday 22 October 2002 03:30 pm, Mike Touloumtzis wrote:
> On Tue, Oct 22, 2002 at 03:13:41PM -0500, Jesse Pollard wrote:
> > On Tuesday 22 October 2002 02:45 pm, Mike Touloumtzis wrote:
> > > Large CVS hosting operations like GNU Savannah have historically used
> > > patches to increase NGROUPS. Using one group per project in CVS is the
> > > sanest way to manage a big repository with complex permissions.
> >
> > OK, I'll bite..
> >
> > Why is this?
>
> I only learned about this by reading the docs on Savannah; the admins can
> provide better information. But my understanding is simply that they have
> M users and N projects, and they want the system to support any number of
> permission pairs from M x N, i.e. they want each user to be able to commit
> to an arbitrary number of projects. And CVS relies on OS permissions.
Thats what I thought. Essentially, all projects are world rw if all users
have access to all projects.
> > I saw the post about having to have access to a lock directory by a
> > cvsuser, but how is that different than having that directory with an
> > ACL entry that includes the cvsuser? Or an ACL that includes the
> > group that the cvsuser is a member of?
>
> I guess they prefer to use traditional Unix permissions rather than ACLs.
> I have the same preference. Unix groups are well supported by tools and
> the kind of permission setup I described above is nicely transparent
> to administer. Granting a user write access to a project is simply
> 'adduser username projectname', and a project can easily support a large
> number of writers without big ACLs.
>
> The issue is not just lock directories, but the right to change any
> file in a project, i.e. full CVS commit access to the project rather
> than anonymous access.
As soon as everyone is in every group you get anonymous access.
You would also have the same result by putting all of the CVS files in
one group.
Or by just making the directories/files world rwx/rw.
> So they would need an ACL on each file in the
> repository, and they would need new files to inherit ACLs from their
> parent directories (I've never used ACLs on Linux but I assume this kind
> of thing is supported).
Actually it depends on the implementation. I believe some of the ACL
specs on a directory can be specified to be inherited (I'll have to check
the POSIX ACL definitions, but I remember a number of capabilities
available on directories that didn't exist for files-- yup - It's called
a "default ACL" and can be used to set UGO access, protection
masking and user acess controls).
In the scenario above, I would most likey specify an ACL to
include specific groups of users. That way it wouldn't necessarily
be equivalent to a world rw access.
--
-------------------------------------------------------------------------
Jesse I Pollard, II
Email: [email protected]
Any opinions expressed are solely my own.
On Tue, 22 Oct 2002, Tim Hockin wrote:
> Jesse Pollard wrote:
>
> > Does it actually work with NFS???? or any networked file system?
> > Most of them limit ngroups to 16 to 32, and cannot send any data
> > if there is an overflow, since that overflow would replace all of the
> > data you try to send/recieve...
>
> NFS has a smaller limit, that is correct. An unfortunate limitation.
>
> > And I really doubt that anybody has 10000 unique groups (or even
> > close to that) running under any system. The center I'm at has
> > some of the largest UNIX systems ever made, and there are only
> > about 600 unique groups over the entire center. The largest number
> > of groups a user can be in is 32. And nobody even comes close.
>
> I'm glad it doesn't affect you. If it was a more common problem, it
> would have been solved a long time ago. It does affect some people,
> though. Maybe they can redesign their group structures, but why not
> remove this arbitrary limit, since we can?
This is a real, if not terribly common problem here too. Thanks for
addressing the issue...
--
- Panu -
On Fri, Oct 25, 2002 at 12:34:20PM +0300, Panu Matilainen wrote:
> On Tue, 22 Oct 2002, Tim Hockin wrote:
>
> > Jesse Pollard wrote:
> >
> > > Does it actually work with NFS???? or any networked file system?
> > > Most of them limit ngroups to 16 to 32, and cannot send any data
> > > if there is an overflow, since that overflow would replace all of the
> > > data you try to send/recieve...
> >
> > NFS has a smaller limit, that is correct. An unfortunate limitation.
>
> This is a real, if not terribly common problem here too. Thanks for
> addressing the issue...
Now i'll poke my stick into the hornets nest...
What i think would be much more usefull and could be
supported by NFS et al would be to allow groups to be
members of other groups.
Method 1 -- explicitly:
example group file extract:
webroot:x:103:www,jim,joy
custadm:x:140:%webroot,bob,carol,ted,alice
webcusts:x:1000:%webcust1,%webcust2,%webcust3
webcust1:x:1001:%custadm,%custwebs,Matt,Christoph
webcust2:x:1002:%custadm,%custwebs,Suparna,Aaron,Tim
webcust3:x:1003:%custadm,%custwebs,Randal,Jesse
I'm using the % prefix here to specify the group
namespace.
It would require permissions checking to aquire a
list of groups that are group members.
Now, changing it at this level would require that
the libs be updated (but so would infinite groups)
and a way to inform the kernel of the nested group
memberships.
For informing the kernel i lean toward a sysfs
interface fed by a user-space utility that would
build or update a pinned table. The in-kernel group
lists would be unrolled (per the example
webroot=custadm,webcust1,webcust2,webcust3)
There would be problems with existing utilities due
to the new logic but that is a fairly small set and
it might not be unreasonable to provide an infinite
NGROUPS emulation. Also multiple inheritance and
loops would have to be caught.
It also provides a way to have 400 (out of 16000)
users in a group without infinite line length in
/etc/group.
Method 2 -- implicitly:
Have the sysfs interface fed by a utility that would
use a separate config file. The group file would be
constructed as though NGROUPS were infinite.
When setgroups is called with size > NGROUPS
it would have to search for any entries that
matched the list (yuck). Match failure would
error with EINVAL
The only change to libs and utilities would be to
lift NGROUPS_MAX. The need for explicity group
numbers would be so it would work over networks.
This method has far too much magic for my taste and
the potential for admin error in maintaining
separate files is frightening.
The implicit method could be restricted to an
extension to NFS but then you would need to have the
match cached in task_struct (reset by setgroups).
The important thing either way would be that you would save
on memory for group lists and it would work over NFS without
a protocol change.
I've actually wanted the nested group memberships for a long
time.
The only other idea I've had for accommodating NFS and other
remote FS for processes having excessive NGROUPS is to have
the client fetch the ownership and ACLs and execute the
access specifying the applicable subset of groups. This
would not be good for performance but might possibly be done
with the existing protocols and might be better
performance-wise than sending kilobytes of GIDs with every
RPC call.
--
________________________________________________________________
J.W. Schultz Pegasystems Technologies
email address: [email protected]
Remember Cernan and Schmitt
> example group file extract:
> webroot:x:103:www,jim,joy
> custadm:x:140:%webroot,bob,carol,ted,alice
> webcusts:x:1000:%webcust1,%webcust2,%webcust3
> webcust1:x:1001:%custadm,%custwebs,Matt,Christoph
> webcust2:x:1002:%custadm,%custwebs,Suparna,Aaron,Tim
> webcust3:x:1003:%custadm,%custwebs,Randal,Jesse
I've always wanted something like this. It really is not too difficult to
do, but it is entirely a library problem.
> Now, changing it at this level would require that
> the libs be updated (but so would infinite groups)
> and a way to inform the kernel of the nested group
> memberships.
unlimited groups requires a TRIVIAL change to libc.
> For informing the kernel i lean toward a sysfs
> interface fed by a user-space utility that would
> build or update a pinned table. The in-kernel group
> lists would be unrolled (per the example
> webroot=custadm,webcust1,webcust2,webcust3)
gahh..Why does the kernel need to know about a group and members? At login
time (or rather, setgroups() time, likely login, but could be other)
getgrent() or whatnot does a full expansion on the nested group file
(handling recursion properly!). You call setgroups() with the full list of
GIDs for your user. The kernel should not know about a group beyond a GID,
unless we're talking about vastly different semantics than traditional users
and groups.
> There would be problems with existing utilities due
problems with things that parse /etc/group. Not problems with things that
use the getgr*() functions.
> It also provides a way to have 400 (out of 16000)
> users in a group without infinite line length in
> /etc/group.
Line length is/was an real issue. Last I tried to do something like having
5000 users in a group, libc would not parse it. Can't say I've tried
lately. That, however, is another purely library problem.
> The important thing either way would be that you would save
> on memory for group lists and it would work over NFS without
> a protocol change.
No, it wouldn't work on NFS except to another system which understands this
scheme. The patch I proposed uses CoW grouplists. This is good
enough for the vast majority of cases - not too many apps call setgroups()
themselves, being a restricted syscall, and all that.
> I've actually wanted the nested group memberships for a long
> time.
So have I, but it is a different problem...Patches should be sent to
glibc developers.