1 files changed, 57 insertions, 149 deletions

diff --git a/drivers/net/ppp_generic.c b/drivers/net/ppp_generic.c
index 714a23035de1..06b448285eb5 100644
--- a/drivers/net/ppp_generic.c
+++ b/drivers/net/ppp_generic.c
@@ -27,6 +27,7 @@
 #include <linux/kmod.h>
 #include <linux/init.h>
 #include <linux/list.h>
+#include <linux/idr.h>
 #include <linux/netdevice.h>
 #include <linux/poll.h>
 #include <linux/ppp_defs.h>
@@ -173,35 +174,13 @@ struct channel {
  */
 
 /*
- * A cardmap represents a mapping from unsigned integers to pointers,
- * and provides a fast "find lowest unused number" operation.
- * It uses a broad (32-way) tree with a bitmap at each level.
- * It is designed to be space-efficient for small numbers of entries
- * and time-efficient for large numbers of entries.
- */
-#define CARDMAP_ORDER	5
-#define CARDMAP_WIDTH	(1U << CARDMAP_ORDER)
-#define CARDMAP_MASK	(CARDMAP_WIDTH - 1)
-
-struct cardmap {
-	int shift;
-	unsigned long inuse;
-	struct cardmap *parent;
-	void *ptr[CARDMAP_WIDTH];
-};
-static void *cardmap_get(struct cardmap *map, unsigned int nr);
-static int cardmap_set(struct cardmap **map, unsigned int nr, void *ptr);
-static unsigned int cardmap_find_first_free(struct cardmap *map);
-static void cardmap_destroy(struct cardmap **map);
-
-/*
  * all_ppp_mutex protects the all_ppp_units mapping.
  * It also ensures that finding a ppp unit in the all_ppp_units map
  * and updating its file.refcnt field is atomic.
  */
 static DEFINE_MUTEX(all_ppp_mutex);
-static struct cardmap *all_ppp_units;
 static atomic_t ppp_unit_count = ATOMIC_INIT(0);
+static DEFINE_IDR(ppp_units_idr);
 
 /*
  * all_channels_lock protects all_channels and last_channel_index,
@@ -270,6 +249,9 @@ static struct channel *ppp_find_channel(int unit);
 static int ppp_connect_channel(struct channel *pch, int unit);
 static int ppp_disconnect_channel(struct channel *pch);
 static void ppp_destroy_channel(struct channel *pch);
+static int unit_get(struct idr *p, void *ptr);
+static void unit_put(struct idr *p, int n);
+static void *unit_find(struct idr *p, int n);
 
 static struct class *ppp_class;
 
@@ -887,7 +869,7 @@ out_chrdev:
 static int
 ppp_start_xmit(struct sk_buff *skb, struct net_device *dev)
 {
-	struct ppp *ppp = (struct ppp *) dev->priv;
+	struct ppp *ppp = netdev_priv(dev);
 	int npi, proto;
 	unsigned char *pp;
 
@@ -932,7 +914,7 @@ ppp_start_xmit(struct sk_buff *skb, struct net_device *dev)
 static int
 ppp_net_ioctl(struct net_device *dev, struct ifreq *ifr, int cmd)
 {
-	struct ppp *ppp = dev->priv;
+	struct ppp *ppp = netdev_priv(dev);
 	int err = -EFAULT;
 	void __user *addr = (void __user *) ifr->ifr_ifru.ifru_data;
 	struct ppp_stats stats;
@@ -972,8 +954,14 @@ ppp_net_ioctl(struct net_device *dev, struct ifreq *ifr, int cmd)
 	return err;
 }
 
+static const struct net_device_ops ppp_netdev_ops = {
+	.ndo_start_xmit = ppp_start_xmit,
+	.ndo_do_ioctl   = ppp_net_ioctl,
+};
+
 static void ppp_setup(struct net_device *dev)
 {
+	dev->netdev_ops = &ppp_netdev_ops;
 	dev->hard_header_len = PPP_HDRLEN;
 	dev->mtu = PPP_MTU;
 	dev->addr_len = 0;
@@ -1684,7 +1672,6 @@ ppp_receive_nonmp_frame(struct ppp *ppp, struct sk_buff *skb)
 			skb->protocol = htons(npindex_to_ethertype[npi]);
 			skb_reset_mac_header(skb);
 			netif_rx(skb);
-			ppp->dev->last_rx = jiffies;
 		}
 	}
 	return;
@@ -2414,13 +2401,12 @@ ppp_create_interface(int unit, int *retp)
 	int ret = -ENOMEM;
 	int i;
 
-	ppp = kzalloc(sizeof(struct ppp), GFP_KERNEL);
-	if (!ppp)
-		goto out;
-	dev = alloc_netdev(0, "", ppp_setup);
+	dev = alloc_netdev(sizeof(struct ppp), "", ppp_setup);
 	if (!dev)
 		goto out1;
 
+	ppp = netdev_priv(dev);
+	ppp->dev = dev;
 	ppp->mru = PPP_MRU;
 	init_ppp_file(&ppp->file, INTERFACE);
 	ppp->file.hdrlen = PPP_HDRLEN - 2;	/* don't count proto bytes */
@@ -2433,18 +2419,25 @@ ppp_create_interface(int unit, int *retp)
 	ppp->minseq = -1;
 	skb_queue_head_init(&ppp->mrq);
 #endif /* CONFIG_PPP_MULTILINK */
-	ppp->dev = dev;
-	dev->priv = ppp;
-
-	dev->hard_start_xmit = ppp_start_xmit;
-	dev->do_ioctl = ppp_net_ioctl;
 
 	ret = -EEXIST;
 	mutex_lock(&all_ppp_mutex);
-	if (unit < 0)
-		unit = cardmap_find_first_free(all_ppp_units);
-	else if (cardmap_get(all_ppp_units, unit) != NULL)
-		goto out2;	/* unit already exists */
+
+	if (unit < 0) {
+		unit = unit_get(&ppp_units_idr, ppp);
+		if (unit < 0) {
+			*retp = unit;
+			goto out2;
+		}
+	} else {
+		if (unit_find(&ppp_units_idr, unit))
+			goto out2; /* unit already exists */
+		else {
+			/* darn, someone is cheating us? */
+			*retp = -EINVAL;
+			goto out2;
+		}
+	}
 
 	/* Initialize the new ppp unit */
 	ppp->file.index = unit;
@@ -2452,29 +2445,22 @@ ppp_create_interface(int unit, int *retp)
 
 	ret = register_netdev(dev);
 	if (ret != 0) {
+		unit_put(&ppp_units_idr, unit);
 		printk(KERN_ERR "PPP: couldn't register device %s (%d)\n",
 		       dev->name, ret);
 		goto out2;
 	}
 
 	atomic_inc(&ppp_unit_count);
-	ret = cardmap_set(&all_ppp_units, unit, ppp);
-	if (ret != 0)
-		goto out3;
-
 	mutex_unlock(&all_ppp_mutex);
+
 	*retp = 0;
 	return ppp;
 
-out3:
-	atomic_dec(&ppp_unit_count);
-	unregister_netdev(dev);
 out2:
 	mutex_unlock(&all_ppp_mutex);
 	free_netdev(dev);
 out1:
-	kfree(ppp);
-out:
 	*retp = ret;
 	return NULL;
 }
@@ -2508,7 +2494,7 @@ static void ppp_shutdown_interface(struct ppp *ppp)
 	} else
 		ppp_unlock(ppp);
 
-	cardmap_set(&all_ppp_units, ppp->file.index, NULL);
+	unit_put(&ppp_units_idr, ppp->file.index);
 	ppp->file.dead = 1;
 	ppp->owner = NULL;
 	wake_up_interruptible(&ppp->file.rwait);
@@ -2562,7 +2548,7 @@ static void ppp_destroy_interface(struct ppp *ppp)
 static struct ppp *
 ppp_find_unit(int unit)
 {
-	return cardmap_get(all_ppp_units, unit);
+	return unit_find(&ppp_units_idr, unit);
 }
 
 /*
@@ -2680,123 +2666,45 @@ static void __exit ppp_cleanup(void)
 	/* should never happen */
 	if (atomic_read(&ppp_unit_count) || atomic_read(&channel_count))
 		printk(KERN_ERR "PPP: removing module but units remain!\n");
-	cardmap_destroy(&all_ppp_units);
 	unregister_chrdev(PPP_MAJOR, "ppp");
 	device_destroy(ppp_class, MKDEV(PPP_MAJOR, 0));
 	class_destroy(ppp_class);
+	idr_destroy(&ppp_units_idr);
 }
 
 /*
- * Cardmap implementation.
+ * Units handling. Caller must protect concurrent access
+ * by holding all_ppp_mutex
  */
-static void *cardmap_get(struct cardmap *map, unsigned int nr)
+
+/* get new free unit number and associate pointer with it */
+static int unit_get(struct idr *p, void *ptr)
 {
-	struct cardmap *p;
-	int i;
+	int unit, err;
 
-	for (p = map; p != NULL; ) {
-		if ((i = nr >> p->shift) >= CARDMAP_WIDTH)
-			return NULL;
-		if (p->shift == 0)
-			return p->ptr[i];
-		nr &= ~(CARDMAP_MASK << p->shift);
-		p = p->ptr[i];
+again:
+	if (idr_pre_get(p, GFP_KERNEL) == 0) {
+		printk(KERN_ERR "Out of memory expanding drawable idr\n");
+		return -ENOMEM;
 	}
-	return NULL;
-}
 
-static int cardmap_set(struct cardmap **pmap, unsigned int nr, void *ptr)
-{
-	struct cardmap *p;
-	int i;
+	err = idr_get_new_above(p, ptr, 0, &unit);
+	if (err == -EAGAIN)
+		goto again;
 
-	p = *pmap;
-	if (p == NULL || (nr >> p->shift) >= CARDMAP_WIDTH) {
-		do {
-			/* need a new top level */
-			struct cardmap *np = kzalloc(sizeof(*np), GFP_KERNEL);
-			if (!np)
-				goto enomem;
-			np->ptr[0] = p;
-			if (p != NULL) {
-				np->shift = p->shift + CARDMAP_ORDER;
-				p->parent = np;
-			} else
-				np->shift = 0;
-			p = np;
-		} while ((nr >> p->shift) >= CARDMAP_WIDTH);
-		*pmap = p;
-	}
-	while (p->shift > 0) {
-		i = (nr >> p->shift) & CARDMAP_MASK;
-		if (p->ptr[i] == NULL) {
-			struct cardmap *np = kzalloc(sizeof(*np), GFP_KERNEL);
-			if (!np)
-				goto enomem;
-			np->shift = p->shift - CARDMAP_ORDER;
-			np->parent = p;
-			p->ptr[i] = np;
-		}
-		if (ptr == NULL)
-			clear_bit(i, &p->inuse);
-		p = p->ptr[i];
-	}
-	i = nr & CARDMAP_MASK;
-	p->ptr[i] = ptr;
-	if (ptr != NULL)
-		set_bit(i, &p->inuse);
-	else
-		clear_bit(i, &p->inuse);
-	return 0;
- enomem:
-	return -ENOMEM;
+	return unit;
 }
 
-static unsigned int cardmap_find_first_free(struct cardmap *map)
+/* put unit number back to a pool */
+static void unit_put(struct idr *p, int n)
 {
-	struct cardmap *p;
-	unsigned int nr = 0;
-	int i;
-
-	if ((p = map) == NULL)
-		return 0;
-	for (;;) {
-		i = find_first_zero_bit(&p->inuse, CARDMAP_WIDTH);
-		if (i >= CARDMAP_WIDTH) {
-			if (p->parent == NULL)
-				return CARDMAP_WIDTH << p->shift;
-			p = p->parent;
-			i = (nr >> p->shift) & CARDMAP_MASK;
-			set_bit(i, &p->inuse);
-			continue;
-		}
-		nr = (nr & (~CARDMAP_MASK << p->shift)) | (i << p->shift);
-		if (p->shift == 0 || p->ptr[i] == NULL)
-			return nr;
-		p = p->ptr[i];
-	}
+	idr_remove(p, n);
 }
 
-static void cardmap_destroy(struct cardmap **pmap)
+/* get pointer associated with the number */
+static void *unit_find(struct idr *p, int n)
 {
-	struct cardmap *p, *np;
-	int i;
-
-	for (p = *pmap; p != NULL; p = np) {
-		if (p->shift != 0) {
-			for (i = 0; i < CARDMAP_WIDTH; ++i)
-				if (p->ptr[i] != NULL)
-					break;
-			if (i < CARDMAP_WIDTH) {
-				np = p->ptr[i];
-				p->ptr[i] = NULL;
-				continue;
-			}
-		}
-		np = p->parent;
-		kfree(p);
-	}
-	*pmap = NULL;
+	return idr_find(p, n);
 }
 
 /* Module/initialization stuff */