Index: arch/ia32/src/mm/tlb.c
===================================================================
--- arch/ia32/src/mm/tlb.c	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/ia32/src/mm/tlb.c	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -47,5 +47,5 @@
 }
 
-/** Invalidate TLB entry for specified page range belonging to specified address space.
+/** Invalidate TLB entries for specified page range belonging to specified address space.
  *
  * @param asid This parameter is ignored as the architecture doesn't support it.
Index: arch/ia64/include/mm/asid.h
===================================================================
--- arch/ia64/include/mm/asid.h	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/ia64/include/mm/asid.h	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -35,8 +35,11 @@
 
 /*
- * ASID_MAX can range from 2^18 - 1 to 2^24 - ,
+ * ASID_MAX can range from 2^18 - 1 to 2^24 - 1,
  * depending on architecture implementation.
  */
 #define ASID_MAX_ARCH	16777215	/* 2^24 - 1 */
 
+#define asid_find_free()	ASID_MAX_ARCH
+#define asid_put_arch(x)
+
 #endif
Index: arch/mips32/Makefile.inc
===================================================================
--- arch/mips32/Makefile.inc	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/mips32/Makefile.inc	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -56,5 +56,5 @@
 
 CONFIG_ASID = y
-
+CONFIG_ASID_FIFO = y
 
 ## Accepted MACHINEs
@@ -114,5 +114,4 @@
 	arch/$(ARCH)/src/debugger.c \
 	arch/$(ARCH)/src/cpu/cpu.c \
-	arch/$(ARCH)/src/mm/asid.c \
 	arch/$(ARCH)/src/mm/frame.c \
 	arch/$(ARCH)/src/mm/page.c \
Index: ch/mips32/src/mm/asid.c
===================================================================
--- arch/mips32/src/mm/asid.c	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ 	(revision )
@@ -1,32 +1,0 @@
-/*
- * Copyright (C) 2005 Martin Decky
- * Copyright (C) 2005 Jakub Jermar
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * - Redistributions of source code must retain the above copyright
- *   notice, this list of conditions and the following disclaimer.
- * - 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.
- * - The name of the author may not be used to endorse or promote products
- *   derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
- */
-
-#include <arch/mm/asid.h>
-#include <typedefs.h>
-
Index: arch/mips32/src/mm/tlb.c
===================================================================
--- arch/mips32/src/mm/tlb.c	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/mips32/src/mm/tlb.c	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -29,4 +29,5 @@
 #include <arch/mm/tlb.h>
 #include <mm/asid.h>
+#include <genarch/mm/asid_fifo.h>
 #include <mm/tlb.h>
 #include <mm/page.h>
@@ -57,4 +58,6 @@
 {
 	int i;
+
+	asid_fifo_init();
 
 	cp0_pagemask_write(TLB_PAGE_MASK_16K);
Index: arch/sparc64/Makefile.inc
===================================================================
--- arch/sparc64/Makefile.inc	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/sparc64/Makefile.inc	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -56,5 +56,5 @@
 
 CONFIG_ASID = y
-
+CONFIG_ASID_FIFO = y
 
 ARCH_SOURCES = \
Index: arch/sparc64/src/mm/tlb.c
===================================================================
--- arch/sparc64/src/mm/tlb.c	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ arch/sparc64/src/mm/tlb.c	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -29,4 +29,5 @@
 #include <arch/mm/tlb.h>
 #include <mm/tlb.h>
+#include <genarch/mm/asid_fifo.h>
 #include <arch/mm/frame.h>
 #include <arch/mm/page.h>
@@ -55,4 +56,6 @@
 	frame_address_t fr;
 	page_address_t pg;
+
+	asid_fifo_init();
 
 	fr.address = config.base;
Index: genarch/Makefile.inc
===================================================================
--- genarch/Makefile.inc	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ genarch/Makefile.inc	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -50,2 +50,6 @@
 		genarch/src/mm/asid.c
 endif
+ifeq ($(CONFIG_ASID_FIFO),y)
+	GENARCH_SOURCES += \
+		genarch/src/mm/asid_fifo.c
+endif
Index: genarch/include/mm/asid_fifo.h
===================================================================
--- genarch/include/mm/asid_fifo.h	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
+++ genarch/include/mm/asid_fifo.h	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -0,0 +1,34 @@
+/*
+ * Copyright (C) 2006 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - 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.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
+ */
+
+#ifndef __ASID_FIFO_H__
+#define __ASID_FIFO_H__
+
+extern void asid_fifo_init(void);
+
+#endif
Index: genarch/src/mm/asid_fifo.c
===================================================================
--- genarch/src/mm/asid_fifo.c	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
+++ genarch/src/mm/asid_fifo.c	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2006 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - 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.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
+ */
+
+#include <genarch/mm/asid_fifo.h>
+#include <arch/mm/asid.h>
+#include <mm/asid.h>
+#include <typedefs.h>
+#include <fifo.h>
+
+/**
+ * FIFO queue containing unassigned ASIDs. 
+ * Can be only accessed when asidlock is held.
+ */
+FIFO_INITIALIZE(free_asids, asid_t, ASIDS_ALLOCABLE);
+
+/** Initialize data structures for O(1) ASID allocation and deallocation. */
+void asid_fifo_init(void)
+{
+	int i;
+	
+	for (i = 0; i < ASIDS_ALLOCABLE; i++) {
+		fifo_push(free_asids, ASID_START + i);
+	}
+}
+
+/** Allocate free ASID.
+ *
+ * Allocation runs in O(1).
+ *
+ * @return Free ASID.
+ */
+asid_t asid_find_free(void)
+{
+	return fifo_pop(free_asids);
+}
+
+/** Return ASID among free ASIDs.
+ *
+ * This operation runs in O(1).
+ *
+ * @param asid ASID being freed.
+ */
+void asid_put_arch(asid_t asid)
+{
+	fifo_push(free_asids, asid);
+}
Index: generic/include/mm/asid.h
===================================================================
--- generic/include/mm/asid.h	(revision 86c9e3706d46f8c4bf342d67f4f7e52881d7eeb2)
+++ generic/include/mm/asid.h	(revision 6ed5352295adcd745ba17129d6c6a4abd72de065)
@@ -55,6 +55,11 @@
 #endif /* !def asid_install */
 
-#define asid_find_free()	ASID_START
-#define asid_put_arch(x)
+#ifndef asid_find_free
+extern asid_t asid_find_free(void);
+#endif /* !def asid_find_free */
+
+#ifndef asid_put_arch
+extern void asid_put_arch(asid_t asid);
+#endif /* !def asid_put_arch */
 
 #endif
