Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Rework the way trees of MergeEngine objects are built in vdbesort.c to make it easier to follow. Fix memory leaks that could follow an OOM or IO error. Add various comments to explain functions in vdbesort.c. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | threads |
Files: | files | file ages | folders |
SHA1: |
69026ec7dc3bd3e33bbe17c221a53cf1 |
User & Date: | dan 2014-04-16 16:43:05.014 |
Context
2014-04-16
| ||
17:41 | Change the name of vdbeIncrInit2 to vdbePmaReaderIncrInit. Add a header comment to the same function. (check-in: 6622d87675 user: dan tags: threads) | |
16:43 | Rework the way trees of MergeEngine objects are built in vdbesort.c to make it easier to follow. Fix memory leaks that could follow an OOM or IO error. Add various comments to explain functions in vdbesort.c. (check-in: 69026ec7dc user: dan tags: threads) | |
2014-04-15
| ||
20:52 | Fix some problems to do with OOM conditions in vdbesort.c. Some problems remain. (check-in: 2f94f9ce9b user: dan tags: threads) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
1748 1749 1750 1751 1752 1753 1754 1755 | } return rc; } /* ** Allocate and return a new IncrMerger object to read data from pMerger. */ | > > > > > | > > > | > > > | < > > > > > > > > > > > > > > > > > | < | > | 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 | } return rc; } /* ** Allocate and return a new IncrMerger object to read data from pMerger. ** ** If an OOM condition is encountered, return NULL. In this case free the ** pMerger argument before returning. */ static int vdbeIncrNew( SortSubtask *pTask, MergeEngine *pMerger, IncrMerger **ppOut ){ int rc = SQLITE_OK; IncrMerger *pIncr = *ppOut = (IncrMerger*)sqlite3_malloc(sizeof(IncrMerger)); if( pIncr ){ memset(pIncr, 0, sizeof(IncrMerger)); pIncr->pMerger = pMerger; pIncr->pTask = pTask; pIncr->mxSz = MAX(pTask->pSorter->mxKeysize+9,pTask->pSorter->mxPmaSize/2); pTask->file2.iEof += pIncr->mxSz; }else{ vdbeMergeEngineFree(pMerger); rc = SQLITE_NOMEM; } return rc; } /* ** Set the "use-threads" flag on object pIncr. */ static void vdbeIncrSetThreads(IncrMerger *pIncr, int bUseThread){ if( bUseThread ){ pIncr->bUseThread = 1; pIncr->pTask->file2.iEof -= pIncr->mxSz; } } #define INCRINIT2_NORMAL 0 #define INCRINIT2_TASK 1 #define INCRINIT2_ROOT 2 static int vdbeIncrInit2(PmaReader *pIter, int eMode); /* ** Initialize the merger argument passed as the second argument. Once this ** function returns, the first key of merged data may be read from the merger ** object in the usual fashion. ** ** If argument eMode is INCRINIT2_ROOT, then it is assumed that any IncrMerge ** objects attached to the PmaReader objects that the merger reads from have ** already been populated, but that they have not yet populated aFile[0] and ** set the PmaReader objects up to read from it. In this case all that is ** required is to call vdbePmaReaderNext() on each iterator to point it at ** its first key. ** ** Otherwise, if eMode is any value other than INCRINIT2_ROOT, then use ** vdbeIncrInit2() to initialize each PmaReader that feeds data to pMerger. ** ** SQLITE_OK is returned if successful, or an SQLite error code otherwise. */ static int vdbeIncrInitMerger( SortSubtask *pTask, MergeEngine *pMerger, int eMode /* One of the INCRINIT2_XXX constants */ ){ int rc = SQLITE_OK; /* Return code */ int i; /* For iterating through PmaReader objects */ for(i=0; rc==SQLITE_OK && i<pMerger->nTree; i++){ if( eMode==INCRINIT2_ROOT ){ rc = vdbePmaReaderNext(&pMerger->aIter[i]); }else{ rc = vdbeIncrInit2(&pMerger->aIter[i], INCRINIT2_NORMAL); } |
︙ | ︙ | |||
1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 | rc = vdbePmaReaderNext(pIter); } } return rc; } #if SQLITE_MAX_WORKER_THREADS>0 static void *vdbeIncrInit2Thread(void *pCtx){ PmaReader *pReader = (PmaReader*)pCtx; void *pRet = SQLITE_INT_TO_PTR( vdbeIncrInit2(pReader, INCRINIT2_TASK) ); pReader->pIncr->pTask->bDone = 1; return pRet; } static int vdbeIncrBgInit2(PmaReader *pIter){ void *pCtx = (void*)pIter; return vdbeSorterCreateThread(pIter->pIncr->pTask, vdbeIncrInit2Thread, pCtx); } #endif /* | > > > > > > > > > > > | 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 | rc = vdbePmaReaderNext(pIter); } } return rc; } #if SQLITE_MAX_WORKER_THREADS>0 /* ** The main routine for vdbeIncrInit2() operations run in background threads. */ static void *vdbeIncrInit2Thread(void *pCtx){ PmaReader *pReader = (PmaReader*)pCtx; void *pRet = SQLITE_INT_TO_PTR( vdbeIncrInit2(pReader, INCRINIT2_TASK) ); pReader->pIncr->pTask->bDone = 1; return pRet; } /* ** Use a background thread to invoke vdbeIncrInit2(INCRINIT2_TASK) on the ** the PmaReader object passed as the first argument. ** ** This call will initialize the various fields of the pIter->pIncr ** structure and, if it is a multi-threaded IncrMerger, launch a ** background thread to populate aFile[1]. */ static int vdbeIncrBgInit2(PmaReader *pIter){ void *pCtx = (void*)pIter; return vdbeSorterCreateThread(pIter->pIncr->pTask, vdbeIncrInit2Thread, pCtx); } #endif /* |
︙ | ︙ | |||
1901 1902 1903 1904 1905 1906 1907 | vdbeMergeEngineFree(pNew); *ppOut = 0; } *piOffset = iOff; return rc; } | < > | > > > > > > > > | < < > > > > > | > > > > > > > > > > > | | < > > | > > > > > | > | < < < | > > > > | > | > > | | > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > | > | > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > | > < < < < < | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | < | < < < > < > < < < < < | 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 | vdbeMergeEngineFree(pNew); *ppOut = 0; } *piOffset = iOff; return rc; } /* ** Return the depth of a tree comprising nPMA PMAs, assuming a fanout of ** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes. ** ** i.e. ** ** nPMA<=16 -> TreeDepth() == 0 ** nPMA<=256 -> TreeDepth() == 1 ** nPMA<=65536 -> TreeDepth() == 2 */ static int vdbeSorterTreeDepth(int nPMA){ int nDepth = 0; i64 nDiv = SORTER_MAX_MERGE_COUNT; while( nDiv < (i64)nPMA ){ nDiv = nDiv * SORTER_MAX_MERGE_COUNT; nDepth++; } return nDepth; } /* ** pRoot is the root of an incremental merge-tree with depth nDepth (according ** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the ** tree, counting from zero. This function adds pLeaf to the tree. ** ** If successful, SQLITE_OK is returned. If an error occurs, an SQLite error ** code is returned and pLeaf is freed. */ static int vdbeSorterAddToTree( SortSubtask *pTask, /* Task context */ int nDepth, /* Depth of tree according to TreeDepth() */ int iSeq, /* Sequence number of leaf within tree */ MergeEngine *pRoot, /* Root of tree */ MergeEngine *pLeaf /* Leaf to add to tree */ ){ int rc = SQLITE_OK; int nDiv = 1; int i; MergeEngine *p = pRoot; IncrMerger *pIncr; rc = vdbeIncrNew(pTask, pLeaf, &pIncr); for(i=1; i<nDepth; i++){ nDiv = nDiv * SORTER_MAX_MERGE_COUNT; } for(i=1; i<nDepth && rc==SQLITE_OK; i++){ int iIter = (iSeq / nDiv) % SORTER_MAX_MERGE_COUNT; PmaReader *pIter = &p->aIter[iIter]; if( pIter->pIncr==0 ){ MergeEngine *pNew = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT); if( pNew==0 ){ rc = SQLITE_NOMEM; }else{ rc = vdbeIncrNew(pTask, pNew, &pIter->pIncr); } } p = pIter->pIncr->pMerger; nDiv = nDiv / SORTER_MAX_MERGE_COUNT; } if( rc==SQLITE_OK ){ p->aIter[iSeq % SORTER_MAX_MERGE_COUNT].pIncr = pIncr; }else{ vdbeIncrFree(pIncr); } return rc; } /* ** This function is called as part of a SorterRewind() operation on a sorter ** that has already written two or more level-0 PMAs to one or more temp ** files. It builds a tree of MergeEngine/IncrMerger/PmaReader objects that ** can be used to incrementally merge all PMAs on disk. ** ** If successful, SQLITE_OK is returned and *ppOut set to point to the ** MergeEngine object at the root of the tree before returning. Or, if an ** error occurs, an SQLite error code is returned and the final value ** of *ppOut is undefined. */ static int vdbeSorterMergeTreeBuild(VdbeSorter *pSorter, MergeEngine **ppOut){ MergeEngine *pMain = 0; int rc = SQLITE_OK; int iTask; /* If the sorter uses more than one task, then create the top-level ** MergeEngine here. This MergeEngine will read data from exactly ** one PmaReader per sub-task. */ assert( pSorter->bUseThreads || pSorter->nTask==1 ); if( pSorter->nTask>1 ){ pMain = vdbeMergeEngineNew(pSorter->nTask); if( pMain==0 ) rc = SQLITE_NOMEM; } for(iTask=0; iTask<pSorter->nTask && rc==SQLITE_OK; iTask++){ SortSubtask *pTask = &pSorter->aTask[iTask]; if( pTask->nPMA ){ MergeEngine *pRoot = 0; /* Root node of tree for this task */ int nDepth = vdbeSorterTreeDepth(pTask->nPMA); i64 iReadOff = 0; if( pTask->nPMA<=SORTER_MAX_MERGE_COUNT ){ rc = vdbeMergeEngineLevel0(pTask, pTask->nPMA, &iReadOff, &pRoot); }else{ int i; int iSeq = 0; pRoot = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT); if( pRoot==0 ) rc = SQLITE_NOMEM; for(i=0; i<pTask->nPMA && rc==SQLITE_OK; i += SORTER_MAX_MERGE_COUNT){ MergeEngine *pMerger = 0; /* New level-0 PMA merger */ int nReader; /* Number of level-0 PMAs to merge */ nReader = MIN(pTask->nPMA - i, SORTER_MAX_MERGE_COUNT); rc = vdbeMergeEngineLevel0(pTask, nReader, &iReadOff, &pMerger); if( rc==SQLITE_OK ){ rc = vdbeSorterAddToTree(pTask, nDepth, iSeq++, pRoot, pMerger); } } } if( rc==SQLITE_OK ){ if( pMain==0 ){ pMain = pRoot; }else{ rc = vdbeIncrNew(pTask, pRoot, &pMain->aIter[iTask].pIncr); } }else{ vdbeMergeEngineFree(pRoot); } } } if( rc!=SQLITE_OK ){ vdbeMergeEngineFree(pMain); pMain = 0; } *ppOut = pMain; return rc; } /* ** Populate iterator *pIter so that it may be used to iterate through all ** keys stored in all PMAs created by this sorter. */ static int vdbePmaReaderIncrInit(VdbeSorter *pSorter){ int rc; /* Return code */ SortSubtask *pTask0 = &pSorter->aTask[0]; MergeEngine *pMain = 0; sqlite3 *db = pTask0->pSorter->db; int iTask; rc = vdbeSorterMergeTreeBuild(pSorter, &pMain); if( rc==SQLITE_OK ){ #if SQLITE_MAX_WORKER_THREADS if( pSorter->bUseThreads ){ PmaReader *pIter; SortSubtask *pLast = &pSorter->aTask[pSorter->nTask-1]; rc = vdbeSortAllocUnpacked(pLast); if( rc==SQLITE_OK ){ pIter = (PmaReader*)sqlite3DbMallocZero(db, sizeof(PmaReader)); pSorter->pReader = pIter; } if( rc==SQLITE_OK ){ rc = vdbeIncrNew(pLast, pMain, &pIter->pIncr); if( rc==SQLITE_OK ){ vdbeIncrSetThreads(pIter->pIncr, pSorter->bUseThreads); for(iTask=0; iTask<(pSorter->nTask-1); iTask++){ IncrMerger *pIncr; if( (pIncr = pMain->aIter[iTask].pIncr) ){ vdbeIncrSetThreads(pIncr, pSorter->bUseThreads); assert( pIncr->pTask!=pLast ); } } if( pSorter->nTask>1 ){ for(iTask=0; rc==SQLITE_OK && iTask<pSorter->nTask; iTask++){ PmaReader *p = &pMain->aIter[iTask]; assert( p->pIncr==0 || p->pIncr->pTask==&pSorter->aTask[iTask] ); if( p->pIncr ){ rc = vdbeIncrBgInit2(p); } } } } pMain = 0; } if( rc==SQLITE_OK ){ int eMode = (pSorter->nTask>1 ? INCRINIT2_ROOT : INCRINIT2_NORMAL); rc = vdbeIncrInit2(pIter, eMode); } }else #endif { rc = vdbeIncrInitMerger(pTask0, pMain, INCRINIT2_NORMAL); pSorter->pMerger = pMain; pMain = 0; } } if( rc!=SQLITE_OK ){ vdbeMergeEngineFree(pMain); } return rc; } /* ** Once the sorter has been populated by calls to sqlite3VdbeSorterWrite, ** this function is called to prepare for iterating through the records |
︙ | ︙ |