Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0151af4

Browse files
committed
Avoid O(N^2) behavior in SyncPostCheckpoint().
As in commits6301c3a ande9d9ba2, avoid doing repetitivelist_delete_first() operations, since that would be expensive whenthere are many files waiting to be unlinked. This is a slightlylarger change than in those cases. We have to keep the list statevalid for calls to AbsorbSyncRequests(), so it's necessary to invent a"canceled" field instead of immediately deleting PendingUnlinkEntryentries. Also, because we might not be able to process all theentries, we need a new list primitive list_delete_first_n().list_delete_first_n() is almost list_copy_tail(), but it modifies theinput List instead of making a new copy. I found a couple of existinguses of the latter that could profitably use the new function. (Theremight be more, but the other callers look like they probably shouldn'toverwrite the input List.)As before, back-patch to v13.Discussion:https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com
1 parente477642 commit0151af4

File tree

5 files changed

+103
-14
lines changed

5 files changed

+103
-14
lines changed

‎src/backend/nodes/list.c

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -891,6 +891,72 @@ list_delete_last(List *list)
891891
returnlist_truncate(list,list_length(list)-1);
892892
}
893893

894+
/*
895+
* Delete the first N cells of the list.
896+
*
897+
* The List is pfree'd if the request causes all cells to be deleted.
898+
*/
899+
List*
900+
list_delete_first_n(List*list,intn)
901+
{
902+
check_list_invariants(list);
903+
904+
/* No-op request? */
905+
if (n <=0)
906+
returnlist;
907+
908+
/* Delete whole list? */
909+
if (n >=list_length(list))
910+
{
911+
list_free(list);
912+
returnNIL;
913+
}
914+
915+
/*
916+
* Otherwise, we normally just collapse out the removed elements. But for
917+
* debugging purposes, move the whole list contents someplace else.
918+
*
919+
* (Note that we *must* keep the contents in the same memory context.)
920+
*/
921+
#ifndefDEBUG_LIST_MEMORY_USAGE
922+
memmove(&list->elements[0],&list->elements[n],
923+
(list->length-n)*sizeof(ListCell));
924+
list->length-=n;
925+
#else
926+
{
927+
ListCell*newelems;
928+
intnewmaxlen=list->length-n;
929+
930+
newelems= (ListCell*)
931+
MemoryContextAlloc(GetMemoryChunkContext(list),
932+
newmaxlen*sizeof(ListCell));
933+
memcpy(newelems,&list->elements[n],newmaxlen*sizeof(ListCell));
934+
if (list->elements!=list->initial_elements)
935+
pfree(list->elements);
936+
else
937+
{
938+
/*
939+
* As in enlarge_list(), clear the initial_elements[] space and/or
940+
* mark it inaccessible.
941+
*/
942+
#ifdefCLOBBER_FREED_MEMORY
943+
wipe_mem(list->initial_elements,
944+
list->max_length*sizeof(ListCell));
945+
#else
946+
VALGRIND_MAKE_MEM_NOACCESS(list->initial_elements,
947+
list->max_length*sizeof(ListCell));
948+
#endif
949+
}
950+
list->elements=newelems;
951+
list->max_length=newmaxlen;
952+
list->length=newmaxlen;
953+
check_list_invariants(list);
954+
}
955+
#endif
956+
957+
returnlist;
958+
}
959+
894960
/*
895961
* Generate the union of two lists. This is calculated by copying
896962
* list1 via list_copy(), then adding to it all the members of list2

‎src/backend/optimizer/util/clauses.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4165,7 +4165,7 @@ add_function_defaults(List *args, HeapTuple func_tuple)
41654165
if (ndelete<0)
41664166
elog(ERROR,"not enough default arguments");
41674167
if (ndelete>0)
4168-
defaults=list_copy_tail(defaults,ndelete);
4168+
defaults=list_delete_first_n(defaults,ndelete);
41694169

41704170
/* And form the combined argument list, not modifying the input list */
41714171
returnlist_concat_copy(args,defaults);

‎src/backend/parser/parse_func.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1679,7 +1679,7 @@ func_get_detail(List *funcname,
16791679

16801680
ndelete=list_length(defaults)-best_candidate->ndargs;
16811681
if (ndelete>0)
1682-
defaults=list_copy_tail(defaults,ndelete);
1682+
defaults=list_delete_first_n(defaults,ndelete);
16831683
*argdefaults=defaults;
16841684
}
16851685
}

‎src/backend/storage/sync/sync.c

Lines changed: 34 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,7 @@ typedef struct
6666
{
6767
FileTagtag;/* identifies handler and file */
6868
CycleCtrcycle_ctr;/* checkpoint_cycle_ctr when request was made */
69+
boolcanceled;/* true if request has been canceled */
6970
}PendingUnlinkEntry;
7071

7172
staticHTAB*pendingOps=NULL;
@@ -174,13 +175,18 @@ void
174175
SyncPostCheckpoint(void)
175176
{
176177
intabsorb_counter;
178+
ListCell*lc;
177179

178180
absorb_counter=UNLINKS_PER_ABSORB;
179-
while (pendingUnlinks!=NIL)
181+
foreach(lc,pendingUnlinks)
180182
{
181-
PendingUnlinkEntry*entry= (PendingUnlinkEntry*)linitial(pendingUnlinks);
183+
PendingUnlinkEntry*entry= (PendingUnlinkEntry*)lfirst(lc);
182184
charpath[MAXPGPATH];
183185

186+
/* Skip over any canceled entries */
187+
if (entry->canceled)
188+
continue;
189+
184190
/*
185191
* New entries are appended to the end, so if the entry is new we've
186192
* reached the end of old entries.
@@ -210,22 +216,40 @@ SyncPostCheckpoint(void)
210216
errmsg("could not remove file \"%s\": %m",path)));
211217
}
212218

213-
/* And remove the list entry */
214-
pendingUnlinks=list_delete_first(pendingUnlinks);
215-
pfree(entry);
219+
/* Mark the list entry as canceled, just in case */
220+
entry->canceled= true;
216221

217222
/*
218223
* As in ProcessSyncRequests, we don't want to stop absorbing fsync
219224
* requests for a long time when there are many deletions to be done.
220-
* We can safely call AbsorbSyncRequests() at this point in the loop
221-
* (note it might try to delete list entries).
225+
* We can safely call AbsorbSyncRequests() at this point in the loop.
222226
*/
223227
if (--absorb_counter <=0)
224228
{
225229
AbsorbSyncRequests();
226230
absorb_counter=UNLINKS_PER_ABSORB;
227231
}
228232
}
233+
234+
/*
235+
* If we reached the end of the list, we can just remove the whole list
236+
* (remembering to pfree all the PendingUnlinkEntry objects). Otherwise,
237+
* we must keep the entries at or after "lc".
238+
*/
239+
if (lc==NULL)
240+
{
241+
list_free_deep(pendingUnlinks);
242+
pendingUnlinks=NIL;
243+
}
244+
else
245+
{
246+
intntodelete=list_cell_number(pendingUnlinks,lc);
247+
248+
for (inti=0;i<ntodelete;i++)
249+
pfree(list_nth(pendingUnlinks,i));
250+
251+
pendingUnlinks=list_delete_first_n(pendingUnlinks,ntodelete);
252+
}
229253
}
230254

231255
/*
@@ -465,17 +489,14 @@ RememberSyncRequest(const FileTag *ftag, SyncRequestType type)
465489
entry->canceled= true;
466490
}
467491

468-
/*Remove matching unlink requests */
492+
/*Cancel matching unlink requests */
469493
foreach(cell,pendingUnlinks)
470494
{
471495
PendingUnlinkEntry*entry= (PendingUnlinkEntry*)lfirst(cell);
472496

473497
if (entry->tag.handler==ftag->handler&&
474498
syncsw[ftag->handler].sync_filetagmatches(ftag,&entry->tag))
475-
{
476-
pendingUnlinks=foreach_delete_current(pendingUnlinks,cell);
477-
pfree(entry);
478-
}
499+
entry->canceled= true;
479500
}
480501
}
481502
elseif (type==SYNC_UNLINK_REQUEST)
@@ -487,6 +508,7 @@ RememberSyncRequest(const FileTag *ftag, SyncRequestType type)
487508
entry=palloc(sizeof(PendingUnlinkEntry));
488509
entry->tag=*ftag;
489510
entry->cycle_ctr=checkpoint_cycle_ctr;
511+
entry->canceled= false;
490512

491513
pendingUnlinks=lappend(pendingUnlinks,entry);
492514

‎src/include/nodes/pg_list.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -560,6 +560,7 @@ extern List *list_delete_int(List *list, int datum);
560560
externList*list_delete_oid(List*list,Oiddatum);
561561
externList*list_delete_first(List*list);
562562
externList*list_delete_last(List*list);
563+
externList*list_delete_first_n(List*list,intn);
563564
externList*list_delete_nth_cell(List*list,intn);
564565
externList*list_delete_cell(List*list,ListCell*cell);
565566

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp