Re: Bug 688602 requires a fundamental change to the memory management.
"Leonardo" <[email protected]> Wed, 12 Apr 2006 15:37:21 +0400
| Newsgroups | gmane.comp.printing.ghostscript.patches |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format.
------=_NextPart_000_002C_01C65E46.FD6600C0
Content-Type: text/plain; format=flowed; charset="koi8-r"; reply-type=original
Content-Transfer-Encoding: 7bit
The last patch is buggy.
Here is a good one.
See log message inside.
Leo.
------=_NextPart_000_002C_01C65E46.FD6600C0
Content-Type: application/octet-stream;
name="patch.txt "
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="patch.txt "
Not ready yet.
This patch works with NO_INVISIBLE_LEVELS 1,
but there are serious problems :
1. The garbager can't collect ref arrays
because they are referred from alloc_change_t::offset =3D=3D =
AC_OFFSET_ALLOCATED .
One way to fix is to change gc_trace with a special handling of=20
such elements.
2. Don't like changes to igcref.c .
The old code used some smart invariants,
which become invalid with=20
alloc_change_t::offset =3D=3D AC_OFFSET_ALLOCATED
elements.
3. Still not sure how the old code hadles empty ref arrays.
It is not completely documented.
We can see that they look as unreferenced objects
during the relocation phase because=20
they have no referred elements,
so that o_back points to chead,
but their relocation is done=20
by the offset stored in the extra element
which appears behind the end.
Maybe that's all, but not sure.
BTW, in most cases the old code
unites them with a non-empty array,
and we couldn't find a practical case
when it is not united. We disabled
the uniting condition to emulate
and study this situation.
=20
[Log message end]
Optimize setting the l_new marks during 'restore'.
DETAILS :
This is a preparation for fixing=20
Bug 688602 "Displaying file with GS-8.53 is much slower than with =
GS-8.51".
Currently the new code is disabled with the macro NO_INVISIBLE_LEVELS
defined in gxalloc.h .=20
When NO_INVISIBLE_LEVELS is zero,=20
an algorithmically equivalent change happens in isave.c,
and othewr modules are not affected.
In this case in isave.c :
1. Factored out a new function mark_allocated.
2. Added a new argument to save_set_new, save_set_new_changes
to know that it is called for an invisible level.
When NO_INVISIBLE_LEVELS is 1 :
1. Invisible save levels are not created.
2. Instead that, it creates a new kind of alloc_change_t element,=20
which is marked with AC_OFFSET_ALLOCATED in the 'offset' field.
Such element points to the beginning of a newly allocated 'ref' array
(either packed or not).
3. The new function alloc_save_change_alloc allocates elements
of the new kind.
4. The new function alloc_save_remove removes such elements when
the object is being removed explicitely.
5. save_set_new is expanded to process the new kind of alloc_change_t =
elements.
With such elements it calls mark_allocated (see above),
so that the effect is same as before the patch.
6. The scanning of allocated objects in save_set_new is removed
due to (3).
7. save_set_new_changes is extended with computing the size of=20
newly allocated 'ref' arrays, which are processed during the scan.
It appears to be close to what save_set_new did while scanning
allocated objects (the variable 'changed').
8. The new field gs_ref_memory_t::scan_limit stores a termination
condition for scanning objects in save_set_new_changes.
The value is stored when save_set_new_changes is called=20
from alloc_save_state as it was for creatng an invisible save level.
Rather the new code doesn't create an invisible level,=20
the scan termination condition work as it were created.
9. save_set_new_changes uses the variable 'changed'
for a proper setting of the termination condition.
The condition is not exactly equivalent to the
old one, because the old code also accounts=20
a scanning of non-ref objects, but the new code
doesn't bother with them. Therefore new termination conditions
appear in some different points than invisible levels did.
Therefore the behavior isn't algorithmically equivalent.
10. The new code always restore to a 'visible' level.
In same time, doing a 'restore', some of l_new marks
may be left unrestored due to the scan tremination condition.
This effect may be considered as caching a reasonable
number of recently changed objects by marking with l_new.
Older changes loose the l_new mark and their further changes
will be stored again in the 'changes' list.=20
This causes an extra growth of the 'changes' list,
but saves the processor time from redundant setting
of multiple l_new marks when save-restore is executed
multiple times after a big number of changes.
Thus NO_INVISIBLE_LEVELS 1 reconstructs the optimization,=20
which was lost while fixing the bug 688153 with the revision 5980.
Rather the behavior isn't strongly equivalent,
the main logic is mostly same.
Now we commit this patch with disabled new code.
We'll enable it separately after the regression testing
of the algorithmically equivalent part.
EXPECTED DIFFERENCES :
None.
[Log message end]
=20
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\gsalloc.c Wed Mar 15 15:04:22 2006
--- files\gs\src\gsalloc.c Wed Apr 12 14:50:54 2006
***************
*** 86,89 ****
--- 86,92 ----
ENUM_PTR3(0, gs_ref_memory_t, streams, names_array, changes);
ENUM_PTR(3, gs_ref_memory_t, saved);
+ #if NO_INVISIBLE_LEVELS
+ ENUM_PTR(4, gs_ref_memory_t, scan_limit);
+ #endif
ENUM_PTRS_END
private RELOC_PTRS_WITH(ref_memory_reloc_ptrs, gs_ref_memory_t *mptr)
***************
*** 92,95 ****
--- 95,101 ----
RELOC_PTR(gs_ref_memory_t, names_array);
RELOC_PTR(gs_ref_memory_t, changes);
+ #if NO_INVISIBLE_LEVELS
+ RELOC_PTR(gs_ref_memory_t, scan_limit);
+ #endif
/* Don't relocate the saved pointer now -- see igc.c for details. =
*/
mptr->reloc_saved =3D RELOC_OBJ(mptr->saved);
***************
*** 323,326 ****
--- 329,336 ----
mem->inherited =3D 0;
mem->changes =3D 0;
+ #if NO_INVISIBLE_LEVELS
+ mem->scan_limit =3D 0;
+ mem->total_scanned =3D 0;
+ #endif
ialloc_reset_free(mem);
}
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\gxalloc.h Wed Mar 15 15:04:25 2006
--- files\gs\src\gxalloc.h Thu Apr 6 17:17:04 2006
***************
*** 27,30 ****
--- 27,32 ----
#include "gxobj.h"
=20
+ #define NO_INVISIBLE_LEVELS 1 /* old code =3D 0, new code =3D 1 */
+=20
/* =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Chunks =
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */
=20
***************
*** 381,384 ****
--- 383,389 ----
int num_contexts; /* # of contexts sharing this VM */
struct alloc_change_s *changes;
+ #if NO_INVISIBLE_LEVELS
+ struct alloc_change_s *scan_limit;
+ #endif
struct alloc_save_s *saved;
long total_scanned;
***************
*** 397,401 ****
gs_public_st_composite(st_ref_memory, gs_ref_memory_t,\
"gs_ref_memory", ref_memory_enum_ptrs, ref_memory_reloc_ptrs)
! #define st_ref_memory_max_ptrs 4 /* streams, names_array, changes, =
saved */
=20
/* Define the procedures for the standard allocator. */
--- 402,406 ----
gs_public_st_composite(st_ref_memory, gs_ref_memory_t,\
"gs_ref_memory", ref_memory_enum_ptrs, ref_memory_reloc_ptrs)
! #define st_ref_memory_max_ptrs 5 /* streams, names_array, changes, =
scan_limit, saved */
=20
/* Define the procedures for the standard allocator. */
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\ialloc.c Wed Mar 15 15:04:20 2006
--- files\gs\src\ialloc.c Wed Apr 12 11:24:20 2006
***************
*** 186,190 ****
chunk_t *pcc =3D mem->pcc;
ref *end;
!=20
obj =3D gs_alloc_struct_array((gs_memory_t *) mem, num_refs + 1,
ref, &st_refs, cname);
--- 186,199 ----
chunk_t *pcc =3D mem->pcc;
ref *end;
! #if NO_INVISIBLE_LEVELS
! ref_packed **ppr =3D 0;
! int code =3D 0;
!=20
! if ((gs_memory_t *)mem !=3D mem->stable_memory) {
! code =3D alloc_save_change_alloc(mem, "gs_alloc_ref_array", =
&ppr);
! if (code < 0)
! return code;
! }
! #endif
obj =3D gs_alloc_struct_array((gs_memory_t *) mem, num_refs + 1,
ref, &st_refs, cname);
***************
*** 211,214 ****
--- 220,227 ----
cl.cp->has_refs =3D true;
}
+ #if NO_INVISIBLE_LEVELS
+ if (ppr)
+ *ppr =3D (ref_packed *)obj;
+ #endif
}
make_array(parr, attrs | mem->space, num_refs, obj);
***************
*** 274,277 ****
--- 287,294 ----
if ((obj_header_t *) obj =3D=3D mem->cc.rcur) {
/* Deallocate the entire refs object. */
+ #if NO_INVISIBLE_LEVELS
+ if ((gs_memory_t *)mem !=3D mem->stable_memory)
+ alloc_save_remove(mem, (ref_packed *)obj, "gs_free_ref_array");
+ #endif
gs_free_object((gs_memory_t *) mem, obj, cname);
mem->cc.rcur =3D 0;
***************
*** 303,306 ****
--- 320,327 ----
ialloc_trace_space(mem), client_name_string(cname),
num_refs, (ulong) obj);
+ #if NO_INVISIBLE_LEVELS
+ if ((gs_memory_t *)mem !=3D mem->stable_memory)
+ alloc_save_remove(mem, (ref_packed *)obj, "gs_free_ref_array");
+ #endif
alloc_free_chunk(cl.cp, mem);
return;
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\idosave.h Wed Mar 15 15:04:33 2006
--- files\gs\src\idosave.h Wed Apr 12 11:34:26 2006
***************
*** 34,37 ****
--- 34,43 ----
int alloc_save_change_in(gs_ref_memory_t *mem, const ref *pcont,
ref_packed *ptr, client_name_t cname);
+ #if NO_INVISIBLE_LEVELS
+ /* Remove an AC_OFFSET_ALLOCATED element. */
+ void alloc_save_remove(gs_ref_memory_t *mem, ref_packed *obj, =
client_name_t cname);
+ /* Allocate a structure for recording an allocation event. */
+ int alloc_save_change_alloc(gs_ref_memory_t *mem, client_name_t cname, =
ref_packed ***ppr);
+ #endif
=20
#endif /* idosave_INCLUDED */
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\igcref.c Wed Mar 15 15:04:41 2006
--- files\gs\src\igcref.c Thu Apr 6 15:53:21 2006
***************
*** 668,671 ****
--- 668,680 ----
r_clear_attrs(pref, l_mark);
src +=3D packed_per_ref;
+ #if NO_INVISIBLE_LEVELS
+ /* The last (the extra) ref may be marked from=20
+ alloc_change_t::offset=3D=3DAC_OFFSET_ALLOCATED,
+ if the extra ref ends an empty ref array. */
+ if (src >=3D end) {
+ src -=3D packed_per_ref;
+ break;
+ }
+ #endif
}
} else
***************
*** 692,697 ****
r_clear_attrs(&rtemp, l_mark);
ref_assign_inline((ref *) dest, &rtemp);
- dest +=3D packed_per_ref;
src +=3D packed_per_ref;
} else { /* check for end of block */
src +=3D packed_per_ref;
--- 701,713 ----
r_clear_attrs(&rtemp, l_mark);
ref_assign_inline((ref *) dest, &rtemp);
src +=3D packed_per_ref;
+ #if NO_INVISIBLE_LEVELS
+ /* The last (the extra) ref may be marked from=20
+ alloc_change_t::offset=3D=3DAC_OFFSET_ALLOCATED,
+ if the extra ref ends an empty ref array. */
+ if (src >=3D end)
+ break;
+ #endif
+ dest +=3D packed_per_ref;
} else { /* check for end of block */
src +=3D packed_per_ref;
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\isave.c Wed Mar 15 15:04:49 2006
--- files\gs\src\isave.c Wed Apr 12 15:04:46 2006
***************
*** 30,34 ****
#include "gsutil.h" /* gs_next_ids prototype */
=20
-=20
/* Structure descriptor */
private_st_alloc_save();
--- 30,33 ----
***************
*** 166,169 ****
--- 165,171 ----
#define AC_OFFSET_STATIC (-2) /* static object */
#define AC_OFFSET_REF (-1) /* dynamic ref */
+ #if NO_INVISIBLE_LEVELS
+ #define AC_OFFSET_ALLOCATED (-3) /* a newly allocated ref array */
+ #endif
short offset; /* if >=3D 0, offset within struct */
};
***************
*** 197,200 ****
--- 199,205 ----
break;
case AC_OFFSET_REF:
+ #if NO_INVISIBLE_LEVELS
+ case AC_OFFSET_ALLOCATED:
+ #endif
RELOC_REF_PTR_VAR(ptr->where);
break;
***************
*** 250,255 ****
private int restore_resources(alloc_save_t *, gs_ref_memory_t *);
private void restore_free(gs_ref_memory_t *);
! private long save_set_new(gs_ref_memory_t *, bool);
! private void save_set_new_changes(gs_ref_memory_t *, bool);
=20
/* Initialize the save/restore machinery. */
--- 255,260 ----
private int restore_resources(alloc_save_t *, gs_ref_memory_t *);
private void restore_free(gs_ref_memory_t *);
! private long save_set_new(gs_ref_memory_t *, bool, bool);
! private void save_set_new_changes(gs_ref_memory_t *, bool, bool);
=20
/* Initialize the save/restore machinery. */
***************
*** 336,341 ****
/* and ones in objects allocated since the last save. */
if (lmem->save_level > 1) {
! long scanned =3D save_set_new(&lsave->state, false);
=20
if ((lsave->state.total_scanned +=3D scanned) > max_repeated_scan) {
/* Do a second, invisible save. */
--- 341,347 ----
/* and ones in objects allocated since the last save. */
if (lmem->save_level > 1) {
! long scanned =3D save_set_new(&lsave->state, false, true);
=20
+ #if !NO_INVISIBLE_LEVELS
if ((lsave->state.total_scanned +=3D scanned) > max_repeated_scan) {
/* Do a second, invisible save. */
***************
*** 365,368 ****
--- 371,377 ----
}
}
+ #else
+ (void)scanned;
+ #endif
}
alloc_set_in_save(dmem);
***************
*** 484,487 ****
--- 493,535 ----
}
=20
+ #if NO_INVISIBLE_LEVELS
+ /* Allocate a structure for recording an allocation event. */
+ int
+ alloc_save_change_alloc(gs_ref_memory_t *mem, client_name_t cname, =
ref_packed ***ppr)
+ {
+ register alloc_change_t *cp;
+=20
+ if (mem->new_mask =3D=3D 0)
+ return 0; /* no saving */
+ cp =3D gs_alloc_struct((gs_memory_t *)mem, alloc_change_t,
+ &st_alloc_change, "alloc_save_change");
+ if (cp =3D=3D 0)
+ return_error(e_VMerror);
+ cp->next =3D mem->changes;
+ cp->where =3D 0;
+ cp->offset =3D AC_OFFSET_ALLOCATED;
+ make_null(&cp->contents);
+ mem->changes =3D cp;
+ *ppr =3D &cp->where;
+ return 1;
+ }
+=20
+ /* Remove an AC_OFFSET_ALLOCATED element. */
+ void
+ alloc_save_remove(gs_ref_memory_t *mem, ref_packed *obj, client_name_t =
cname)
+ {
+ alloc_change_t **cpp =3D &mem->changes;
+ =20
+ for (; *cpp !=3D NULL; cpp =3D &(*cpp)->next) {
+ alloc_change_t *cp =3D *cpp;
+=20
+ if (cp->offset =3D=3D AC_OFFSET_ALLOCATED && cp->where =3D=3D obj) {
+ *cpp =3D cp->next;
+ gs_free_object((gs_memory_t *)mem, cp, "alloc_save_remove");
+ }
+ }
+ }
+ #endif
+=20
/* Return (the id of) the innermost externally visible save object, */
/* i.e., the innermost save with a non-zero ID. */
***************
*** 694,698 ****
alloc_set_not_in_save(dmem);
} else { /* Set the l_new attribute in all slots that are now =
new. */
! save_set_new(mem, true);
}
=20
--- 742,746 ----
alloc_set_not_in_save(dmem);
} else { /* Set the l_new attribute in all slots that are now =
new. */
! save_set_new(mem, true, false);
}
=20
***************
*** 720,723 ****
--- 768,776 ----
}
#endif
+ #if NO_INVISIBLE_LEVELS
+ if (cp->offset =3D=3D AC_OFFSET_ALLOCATED)
+ DO_NOTHING;
+ else
+ #endif
if (r_is_packed(&cp->contents))
*cp->where =3D *(ref_packed *) & cp->contents;
***************
*** 891,895 ****
alloc_change_t *chp =3D mem->changes;
=20
! save_set_new(&sprev->state, true);
/* Concatenate the changes chains. */
if (chp =3D=3D 0)
--- 944,948 ----
alloc_change_t *chp =3D mem->changes;
=20
! save_set_new(&sprev->state, true, false);
/* Concatenate the changes chains. */
if (chp =3D=3D 0)
***************
*** 904,908 ****
} else {
forget_changes(mem);
! save_set_new(mem, false);
file_forget_save(mem);
combine_space(mem); /* combine memory */
--- 957,961 ----
} else {
forget_changes(mem);
! save_set_new(mem, false, false);
file_forget_save(mem);
combine_space(mem); /* combine memory */
***************
*** 912,916 ****
if (mem !=3D save->space_local && mem->saved !=3D 0) {
forget_changes(mem);
! save_set_new(mem, false);
file_forget_save(mem);
combine_space(mem);
--- 965,969 ----
if (mem !=3D save->space_local && mem->saved !=3D 0) {
forget_changes(mem);
! save_set_new(mem, false, false);
file_forget_save(mem);
combine_space(mem);
***************
*** 1015,1018 ****
--- 1068,1076 ----
=20
if_debug1('U', "[U]forgetting change 0x%lx\n", (ulong) chp);
+ #if NO_INVISIBLE_LEVELS
+ if (chp->offset =3D=3D AC_OFFSET_ALLOCATED)
+ DO_NOTHING;
+ else
+ #endif
if (!r_is_packed(prp))
r_clear_attrs((ref *) prp, l_new);
***************
*** 1045,1071 ****
/* ------ Internal routines ------ */
=20
! /* Set or reset the l_new attribute in every relevant slot. */
! /* This includes every slot on the current change chain, */
! /* and every (ref) slot allocated at this save level. */
! /* Return the number of bytes of data scanned. */
! private long
! save_set_new(gs_ref_memory_t * mem, bool to_new)
{
! long scanned =3D 0;
!=20
! /* Handle the change chain. */
! save_set_new_changes(mem, to_new);
!=20
! /* Handle newly allocated ref objects. */
! SCAN_MEM_CHUNKS(mem, cp) {
! if (cp->has_refs) {
! bool has_refs =3D false;
!=20
! SCAN_CHUNK_OBJECTS(cp)
! DO_ALL
! if_debug3('U', "[U]set_new scan(0x%lx(%u), %d)\n",
! (ulong) pre, size, to_new);
! if (pre->o_type =3D=3D &st_refs) {
! /* These are refs, scan them. */
ref_packed *prp =3D (ref_packed *) (pre + 1);
ref_packed *next =3D (ref_packed *) ((char *)prp + size);
--- 1103,1111 ----
/* ------ Internal routines ------ */
=20
! private inline uint
! mark_allocated(void *obj, bool to_new)
{ =20
! obj_header_t *pre =3D (obj_header_t *)obj - 1;
! uint size =3D pre_obj_contents_size(pre);
ref_packed *prp =3D (ref_packed *) (pre + 1);
ref_packed *next =3D (ref_packed *) ((char *)prp + size);
***************
*** 1077,1084 ****
#endif
=20
- if_debug2('U', "[U]refs 0x%lx to 0x%lx\n",
- (ulong) prp, (ulong) next);
- has_refs =3D true;
- scanned +=3D size;
/* We know that every block of refs ends with */
/* a full-size ref, so we only need the end check */
--- 1117,1120 ----
***************
*** 1106,1109 ****
--- 1142,1175 ----
}
#undef RP_REF
+ return size;
+ }
+=20
+ /* Set or reset the l_new attribute in every relevant slot. */
+ /* This includes every slot on the current change chain, */
+ /* and every (ref) slot allocated at this save level. */
+ /* Return the number of bytes of data scanned. */
+ private long
+ save_set_new(gs_ref_memory_t * mem, bool to_new, bool set_limit)
+ {
+ long scanned =3D 0;
+=20
+ /* Handle the change chain. */
+ save_set_new_changes(mem, to_new, set_limit);
+=20
+ #if !NO_INVISIBLE_LEVELS
+ /* Handle newly allocated ref objects. */
+ SCAN_MEM_CHUNKS(mem, cp) {
+ if (cp->has_refs) {
+ bool has_refs =3D false;
+=20
+ SCAN_CHUNK_OBJECTS(cp)
+ DO_ALL
+ if_debug3('U', "[U]set_new scan(0x%lx(%u), %d)\n",
+ (ulong) pre, size, to_new);
+ if (pre->o_type =3D=3D &st_refs) {
+ /* These are refs, scan them. */
+ ref_packed *prp =3D (ref_packed *) (pre + 1);
+=20
+ scanned +=3D mark_allocated(prp, to_new);
} else
scanned +=3D sizeof(obj_header_t);
***************
*** 1115,1118 ****
--- 1181,1185 ----
if_debug2('u', "[u]set_new (%s) scanned %ld\n",
(to_new ? "restore" : "save"), scanned);
+ #endif
return scanned;
}
***************
*** 1120,1129 ****
/* Set or reset the l_new attribute on the changes chain. */
private void
! save_set_new_changes(gs_ref_memory_t * mem, bool to_new)
{
register alloc_change_t *chp =3D mem->changes;
register uint new =3D (to_new ? l_new : 0);
=20
for (; chp; chp =3D chp->next) {
ref_packed *prp =3D chp->where;
=20
--- 1187,1206 ----
/* Set or reset the l_new attribute on the changes chain. */
private void
! save_set_new_changes(gs_ref_memory_t * mem, bool to_new, bool =
set_limit)
{
register alloc_change_t *chp =3D mem->changes;
register uint new =3D (to_new ? l_new : 0);
+ #if NO_INVISIBLE_LEVELS
+ long scanned =3D mem->total_scanned;
+ #endif
=20
for (; chp; chp =3D chp->next) {
+ #if NO_INVISIBLE_LEVELS
+ if (chp->offset =3D=3D AC_OFFSET_ALLOCATED) {
+ if (chp->where !=3D 0)
+ scanned +=3D mark_allocated((void *)chp->where, to_new);
+ } else
+ #endif
+ {
ref_packed *prp =3D chp->where;
=20
***************
*** 1137,1139 ****
--- 1214,1230 ----
}
}
+ #if NO_INVISIBLE_LEVELS
+ if (mem->scan_limit =3D=3D chp)
+ break;
+ #endif
+ }
+ #if NO_INVISIBLE_LEVELS
+ if (set_limit) {
+ if (scanned >=3D max_repeated_scan) {
+ mem->scan_limit =3D mem->changes;
+ mem->total_scanned =3D 0;
+ } else
+ mem->total_scanned =3D scanned;
+ }
+ #endif
}
=20
------=_NextPart_000_002C_01C65E46.FD6600C0
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
gs-code-review mailing list
[email protected]
http://www.ghostscript.com/mailman/listinfo/gs-code-review
------=_NextPart_000_002C_01C65E46.FD6600C0--