{"push_id":728776294,"size":1,"distinct_size":1,"ref":"refs/heads/REL9_3_STABLE","head":"730089d879751d890ecdfbc4b5cba04440ae4af2","before":"dc5075fed0e1f50ff88adfa6012ab17d5c8f4351","commits":[{"sha":"730089d879751d890ecdfbc4b5cba04440ae4af2","author":{"email":"ffeaa947aef224da9ba99b6a18bdd74288df0e3e@sss.pgh.pa.us","name":"Tom Lane"},"message":"Fix a low-probability crash in our qsort implementation.\n\nIt's standard for quicksort implementations, after having partitioned the\ninput into two subgroups, to recurse to process the smaller partition and\nthen handle the larger partition by iterating.  This method guarantees\nthat no more than log2(N) levels of recursion can be needed.  However,\nBentley and McIlroy argued that checking to see which partition is smaller\nisn't worth the cycles, and so their code doesn't do that but just always\nrecurses on the left partition.  In most cases that's fine; but with\nworst-case input we might need O(N) levels of recursion, and that means\nthat qsort could be driven to stack overflow.  Such an overflow seems to\nbe the only explanation for today's report from Yiqing Jin of a SIGSEGV\nin med3_tuple while creating an index of a couple billion entries with a\nvery large maintenance_work_mem setting.  Therefore, let's spend the few\nadditional cycles and lines of code needed to choose the smaller partition\nfor recursion.\n\nAlso, fix up the qsort code so that it properly uses size_t not int for\nsome intermediate values representing numbers of items.  This would only\nbe a live risk when sorting more than INT_MAX bytes (in qsort/qsort_arg)\nor tuples (in qsort_tuple), which I believe would never happen with any\ncaller in the current core code --- but perhaps it could happen with\ncall sites in third-party modules?  In any case, this is trouble waiting\nto happen, and the corrected code is probably if anything shorter and\nfaster than before, since it removes sign-extension steps that had to\nhappen when converting between int and size_t.\n\nIn passing, move a couple of CHECK_FOR_INTERRUPTS() calls so that it's\nnot necessary to preserve the value of \"r\" across them, and prettify\nthe output of gen_qsort_tuple.pl a little.\n\nBack-patch to all supported branches.  The odds of hitting this issue\nare probably higher in 9.4 and up than before, due to the new ability\nto allocate sort workspaces exceeding 1GB, but there's no good reason\nto believe that it's impossible to crash older branches this way.","distinct":true,"url":"https://api.github.com/repos/postgres/postgres/commits/730089d879751d890ecdfbc4b5cba04440ae4af2"}]}