Vladimir Marangozov's long-awaited malloc restructuring.
For more comments, read the patches@python.org archives.
For documentation read the comments in mymalloc.h and objimpl.h.

(This is not exactly what Vladimir posted to the patches list; I've
made a few changes, and Vladimir sent me a fix in private email for a
problem that only occurs in debug mode.  I'm also holding back on his
change to main.c, which seems unnecessary to me.)
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index 698114e..1df95d7 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -1875,7 +1875,7 @@
 		else { /* strip trailing '\n' */
 			result = PyString_FromStringAndSize(s, strlen(s)-1);
 		}
-		free(s);
+		PyMem_FREE(s);
 		return result;
 	}
 	if (v != NULL) {
diff --git a/Python/ceval.c b/Python/ceval.c
index d0958bd..1a21ee7 100644
--- a/Python/ceval.c
+++ b/Python/ceval.c
@@ -2558,7 +2558,8 @@
 		class);
 	
 	Py_DECREF(arg);
-	PyMem_XDEL(k);
+	if (k != NULL)
+		PyMem_DEL(k);
 	
 	return result;
 }
diff --git a/Python/compile.c b/Python/compile.c
index 58354c6..a387317 100644
--- a/Python/compile.c
+++ b/Python/compile.c
@@ -112,7 +112,7 @@
 	Py_XDECREF(co->co_filename);
 	Py_XDECREF(co->co_name);
 	Py_XDECREF(co->co_lnotab);
-	PyMem_DEL(co);
+	PyObject_DEL(co);
 }
 
 static PyObject *
diff --git a/Python/import.c b/Python/import.c
index a65614c..c224752 100644
--- a/Python/import.c
+++ b/Python/import.c
@@ -124,7 +124,7 @@
 		++countD;
 	for (scan = _PyImport_StandardFiletab; scan->suffix != NULL; ++scan)
 		++countS;
-	filetab = malloc((countD + countS + 1) * sizeof(struct filedescr));
+	filetab = PyMem_NEW(struct filedescr, countD + countS + 1);
 	memcpy(filetab, _PyImport_DynLoadFiletab,
 	       countD * sizeof(struct filedescr));
 	memcpy(filetab + countD, _PyImport_StandardFiletab,
@@ -2398,10 +2398,10 @@
 }
 
 
-/* API for embedding applications that want to add their own entries to the
-   table of built-in modules.  This should normally be called *before*
-   Py_Initialize().  When the malloc() or realloc() call fails, -1 is returned
-   and the existing table is unchanged.
+/* API for embedding applications that want to add their own entries
+   to the table of built-in modules.  This should normally be called
+   *before* Py_Initialize().  When the table resize fails, -1 is
+   returned and the existing table is unchanged.
 
    After a similar function by Just van Rossum. */
 
@@ -2422,10 +2422,8 @@
 		;
 
 	/* Allocate new memory for the combined table */
-	if (our_copy == NULL)
-		p = malloc((i+n+1) * sizeof(struct _inittab));
-	else
-		p = realloc(our_copy, (i+n+1) * sizeof(struct _inittab));
+	p = our_copy;
+	PyMem_RESIZE(p, struct _inittab, i+n+1);
 	if (p == NULL)
 		return -1;
 
diff --git a/Python/marshal.c b/Python/marshal.c
index 05ac6e9..fe9e000 100644
--- a/Python/marshal.c
+++ b/Python/marshal.c
@@ -514,17 +514,17 @@
 			PyErr_SetString(PyExc_ValueError, "bad marshal data");
 			return NULL;
 		}
-		buffer = (char *)Py_Malloc(n);
+		buffer = PyMem_NEW(char, n);
 		if (buffer == NULL)
-		    return NULL;
+			return PyErr_NoMemory();
 		if (r_string(buffer, (int)n, p) != n) {
-			free(buffer);
+			PyMem_DEL(buffer);
 			PyErr_SetString(PyExc_EOFError,
 				"EOF read where object expected");
 			return NULL;
 		}
 		v = PyUnicode_DecodeUTF8(buffer, n, NULL);
-		free(buffer);
+		PyMem_DEL(buffer);
 		return v;
 	    }
 	    
diff --git a/Python/pythonrun.c b/Python/pythonrun.c
index 49e616e..ee6ce07 100644
--- a/Python/pythonrun.c
+++ b/Python/pythonrun.c
@@ -543,7 +543,7 @@
 	if (n == NULL) {
 		if (err.error == E_EOF) {
 			if (err.text)
-				free(err.text);
+				PyMem_DEL(err.text);
 			return E_EOF;
 		}
 		err_input(&err);
@@ -1009,7 +1009,7 @@
 	v = Py_BuildValue("(ziiz)", err->filename,
 			    err->lineno, err->offset, err->text);
 	if (err->text != NULL) {
-		free(err->text);
+		PyMem_DEL(err->text);
 		err->text = NULL;
 	}
 	switch (err->error) {
diff --git a/Python/traceback.c b/Python/traceback.c
index e1148cd..0b8157d 100644
--- a/Python/traceback.c
+++ b/Python/traceback.c
@@ -71,7 +71,7 @@
 	Py_TRASHCAN_SAFE_BEGIN(tb)
 	Py_XDECREF(tb->tb_next);
 	Py_XDECREF(tb->tb_frame);
-	PyMem_DEL(tb);
+	PyObject_DEL(tb);
 	Py_TRASHCAN_SAFE_END(tb)
 }