SQLite入门与分析(七)---浅谈SQLite的虚拟机
写在前面:虚拟机技术在现在是一个非常热的技术,它的历史也很悠久。最早的虚拟机可追溯到IBM的VM/370,到上个世纪90年代,在计算机程序设计语言领域又出现一件革命性的事情——Java语言的出现,它与c++最大的不同在于它必须在Java虚拟机上运行。Java虚拟机掀起了虚拟机技术的热潮,随后,Microsoft也不甘落后,雄心勃勃的推出了.Net平台。由于在这里主要讨论SQLite的虚拟机,不打算对这些做过多评论,但是作为对比,我会先对Java虚拟机作一个概述。好了,下面进入正题。 1、概述 虚拟机一般都采用了基于栈的架构,这种架构易于实现。虚拟机方法显著提高了程序语言的可移植性和安全性,但同时也导致了执行效率的下降。 2、Java虚拟机2.1、概述 Java虚拟机的主要任务是装载Class文件并执行其中的字节码。Java虚拟机包含一个类装载器(class loader),它从程序和API中装载class文件,Java API中只有程序执行时需要的那些类才会被装载,字节码由执行引擎来执行。 不同的Java虚拟机,执行引擎的实现可能不同。在软件实现的虚拟机中,一般有几下几中实现方式: (1) 解释执行:实现简单,但速度较慢,这是Java最初阶段的实现方式。 (2) 即时编译(just-in-time):执行较快,但消耗内存。在这种情况下,第一次执行的字节码会编译成本地机器代码,然后被缓存,以后可以重用。 (3) 自适应优化器:虚拟机开始的时候解释字节码,但是会监视程序的运行,并记录下使用最频繁的代码,然后把这些代码编译成本地代码,而其它的代码仍保持为字节码。该方法既提高的运行速度,又减少了内存开销。 同样,虚拟机也可由硬件来实现,它用本地方法执行Java字节码。 2.2、Java虚拟机 Java虚拟机的结构分为:类装载子系统,运行时数据区,执行引擎,本地方法接口。其中运行时数据区又分为:方法区,堆,Java栈,PC寄存器,本地方法栈。
关于Java虚拟机就介绍到此,由于Java虚拟机内容庞大,在这里不可能一一介绍,如果想更多了解Java虚拟机,参见《深入Java虚拟机》。 3、SQLite虚拟机 在SQLite的后端(backend)的上一层,通常叫做虚拟数据库引擎(virtual database engine),或者叫做虚拟机(virtual machine)。从作用上来说,它是SQLite的核心。用户程序发出的SQL语句请求,由前端(frontend)编译器(以后会继续介绍)处理,生成字节代码程序(bytecode programs),然后由VM解释执行。VM执行时,又会调用B-tree模块的相关的接口,并输出执行的结果(本节将以一个具体的查询过程来描述这一过程)。 3.1、虚拟机的内部结构 先来看一个简单的例子: int main( int argc, char ** argv){ int rc,i,id,cid; char * name; char * sql; char * zErr; sqlite3 * db;sqlite3_stmt * stmt; sql = " selectid,name,cidfromepisodes " ; // 打开数据库 sqlite3_open( test.db " , & db); 编译sql语句 sqlite3_prepare(db,sql,strlen(sql), & stmt,NULL); 调用VM,执行VDBE程序 rc = sqlite3_step(stmt); while (rc == SQLITE_ROW){ id = sqlite3_column_int(stmt, 0 ); name = ( char * )sqlite3_column_text(stmt,128)">1 ); cid = sqlite3_column_int(stmt,128)">2 ); if (name != NULL){ fprintf(stderr,0)">Row:id=%i,cid=%i,name='%s'n } else { /* FieldisNULL */ fprintf(stderr,name=NULLn } rc = sqlite3_step(stmt); } 释放资源 sqlite3_finalize(stmt); 关闭数据库 sqlite3_close(db); return 0 ; } 这段程序很简单,它的功能就是遍历整个表,并把查询结果输出。 vdbe的定义: Code 由vdbe的定义,可以总结出SQLite虚拟机的内部结构: 3.2、指令 int nOp; Numberofinstructionsintheprogram(指令的条数) */Op * aOp; Spacetoholdthevirtualmachine'sprogram(指令) */ aOp数组保存有SQL经过编译后生成的所有指令,对于上面的例子为: 0 、Goto( 0x5b - 91 ) | 0 | 0c1 、Integer( 0x2d - 45 ) | 0 | 0 2 、OpenRead( 0x0c - 12 ) | 2 3 、SetNumColumns( 0x64 - 100 ) | 03 4 、Rewind( 0x77 - 119 ) | 0 | 0a 5 、Rowid( 0x23 - 35 ) | 6 、Column( 0x02 - 2 ) | 1 7 、Column( 8 、Callback( 0x36 - 54 ) | 3 | 9 、Next( 0x68 ) | 5 10 、Close 11 、Halt 12 、Transaction( 0x66 - 102 ) | 13 、VerifyCookie( 0x61 - 97 ) | 14 、Goto( 1 | sqlite3_step()引起VDBE解释引擎执行这段代码,下面来分析该段指令的执行过程: Goto:这是一条跳转指令,它的作用仅仅是跳到第12条指令; SetNumColumns:对P1确定的游标的列数设置为P2(在这里为3),在OP_Column指令执行前,该指令应该被调用来 设置表的列数; Rewind:移动当前游标(P1)移到表或索引的第一条记录; Callback:该指令执行后,PC将指向下一条指令。该指令的执行会结束sqlite3_step()的运行,并向其返回 SQLITE_ROW ——如果存在记录的话;并将VDBE的PC指针指向下一条指令——即Next指令,所以当 重新 调用sqlite3_step()执行VDBE程序时,会执行Next指令 (具体的分析见后面的指令实例分析); Next:将游标移到下一条记录,并将PC指向第5条指令; 3.3、栈 Mem * aStack; Theoperandstack,exceptstringvalues(栈空间) */Mem * pTos; Topentryintheoperandstack(栈顶指针) aStack是VDBE执行时使用的栈,它主要用来保指令执行进需要的参数,以及指令执行时产生的中间结果(参见后面的指令实例分析)。 在计算机硬件领域,基于寄存器的架构已经压倒基于栈的架构成为当今的主流,但是在解释性的虚拟机领域,基于栈架构的实现占了上风。 1. 从编译的角度来看,许多编程语言可以很容易地被编译成栈架构机器语言。如果采用寄存器架构,编译器为了获得好的性能必须进行优化,如全局寄存器分配(这需要对数据流进行分析)。这种复杂的优化工作使虚拟机的便捷性大打折扣。 2. 如果采用寄存器架构,虚拟机必须经常保存和恢复寄存器中的内容。与硬件计算机相比,这些操作在虚拟机中的开销要大得多。因为每一条虚拟机指令都需要进行很费时的指令分派操作。虽然其它的指令也要分派,但是它们的语义内容更丰富。 3. 采用寄存器架构时,指令对应的操作数位于不同寄存器中,对操作数的寻址也是一个问题。而在基于栈的虚拟机中,操作数位于栈顶或紧跟在虚拟机指令之后。由于基于栈的架构的简便性,一些查询语言的实现也采用了此种架构。 SQLite的虚拟机就是基于栈架构的实现。每一个vdbe都有一个栈顶指针,它保存着vdbe的初始栈顶值。而在解释引擎中也有一个pTos,它们是有区别的: (1)vdbe的pTos:在一趟vdbe执行的过程中不会变化,直到相应的指令修改它为止,在上面的例子中,Callback指令会修改其值(见指令分析)。 (2)而解释引擎中的pTos是随着指令的执行而动态变化的,在上面的例子中,Integer,Column指令的执行都会引起解释引擎pTos的改变。 3.4、指令计数器(PC) **或者返回SQLITE_ROW. */ int sqlite3VdbeExec( Vdbe * p TheVDBE */ ){ 指令计数器 int pc; Theprogramcounter 当前指令 Op * pOp; Currentoperation int rc = SQLITE_OK; Valuetoreturn 数据库 sqlite3 * db = p -> db; Thedatabase */ u8encoding = ENC(db); Thedatabaseencoding 栈顶 Mem * pTos; Topentryintheoperandstack */ if (p -> magic != VDBE_MAGIC_RUN) return SQLITE_MISUSE; 当前栈顶指针 pTos = p -> pTos; if (p -> rc == SQLITE_NOMEM){ Thishappensifamalloc()insideacalltosqlite3_column_text()or **sqlite3_column_text16()failed. goto no_mem; } p -> rc = SQLITE_OK; 如果需要进行出栈操作,则进行出栈操作 if (p -> popStack){ popStack( & pTos,p -> popStack); p -> popStack = 0 ; } 表明栈中没有结果 p -> resOnStack = 0 ; db -> busyHandler.nBusy = 0 ; 执行指令 for (pc = p -> pc;rc == SQLITE_OK;pc ++ ){ 取出操作码 pOp = & p -> aOp[pc]; switch (pOp -> opcode){ 跳到操作数P2指向的指令 case OP_Goto:{ no-push */ CHECK_FOR_INTERRUPT; 设置pc pc = pOp -> p2 - 1 ; break ; } P1入栈 case OP_Integer:{ 当前栈顶指针上移 pTos ++ ; 设为整型 pTos -> flags = MEM_Int; 取操作数P1,并赋值 pTos -> i = pOp -> p1; 其它指令的实现 } endswitch endfor } 3.6、指令实例分析 由于篇幅限制,仅给出几条的指令的实现,其它具体实现见源码。 1、Callback指令 /*该指令执行后,PC将指向下一条指令. **栈中栈顶的P1个值为查询的结果.该指令会导致sqlite3_step()函数将以SQLITE_ROW为返回码 **而结束运行.此时用户程序就可以通过sqlite3_column_XXX读取位于栈中的数据了. **当sqlite3_step()再一次运行时,栈顶的P1个值会在执行Next指令前自动出栈. */ caseOP_Callback:{no-push*/ Mem*pMem; Mem*pFirstColumn; assert(p->nResColumn==pOp->p1); Datainthepagermightbemovedorchangedoutfromunderus **inbetweenthereturnfromthissqlite3_step()callandthe **nextcalltosqlite3_step().Sodeephermeralizeeverythingon **thestack.Notethatephemeraldataisneverstoredinmemory **cellssowedonothavetoworryaboutthem. */ pFirstColumn=&pTos[0-pOp->p1]; for(pMem=p->aStack;pMem<pFirstColumn;pMem++){ Deephemeralize(pMem); } Invalidateallephemeralcursorrowcaches*/ p->cacheCtr=(p->cacheCtr+2)|1; Makesuretheresultsofthecurrentroware 00terminated **andhaveanassignedtype.Theresultsaredeephemeralizedas **assideeffect. for(;pMem<=pTos;pMem++){ sqlite3VdbeMemNulTerminate(pMem); //设置结果集中的数据类型 storeTypeInfo(pMem,encoding); } Setupthestatementstructuresothatitwillpopthecurrent **resultsfromthestackwhenthestatementreturns. */ p->resOnStack=1;栈上有结果 p->nCallback++;回调次数加1 出栈的数据个数,在下次执行VDBE时,会先进行出栈操作 p->popStack=pOp->p1; 程序计数器加1 p->pc=pc+设置vdbe的栈顶指针,此时,栈中保存有结果 p->pTos=pTos; 注意:这里不是break,而是return;向sqlite3_step()返回SQLITE_ROW. **当用户程序重新调用sqlite3_step()时,重新执行VDBE. returnSQLITE_ROW; } 2、Rewind指令 移动当前游标到表或索引的第一条记录. **如果表为空且p2>0,则跳到p2处;如果p2为0且表不空,则执行下一条指令. caseOP_Rewind:{inti=pOp->p1; Cursor*pC; BtCursor*pCrsr; intres; assert(i>=0&&i<p->nCursor); 取得当前游标 pC=p->apCsr[i]; assert(pC!=0); if((pCrsr=pC->pCursor)!=0){ 调用B-tree模块,移动游标到第一条记录 rc=sqlite3BtreeFirst(pCrsr,&res); pC->atFirst=res==0; pC->deferredMoveto=0; pC->cacheStatus=CACHE_STALE; }else{ res=1; } pC->nullRow=res; if(res&&pOp->p2>0){ pc=pOp->p2-1; } break; } 3、Column指令 解析当前游标指定的记录的数据 **p1为当前游标索引号,p2为列号 caseOP_Column:{ u32payloadSize;Numberofbytesintherecordintp1=pOp->p1;P1valueoftheopcode列号 intp2=pOp->p2;columnnumbertoretrieveVDBE游标 Cursor*pC=0;TheVDBEcursorchar*zRec;Pointertocompleterecord-databtree游标 BtCursor*pCrsr;TheBTreecursor*/ u32*aType;aType[i]holdsthenumerictypeofthei-thcolumn*/ u32*aOffset;aOffset[i]isoffsettostartofdatafori-thcolumn列数 u32nField;numberoffieldsintherecordintlen;Thelengthoftheserializeddataforthecolumninti;Loopcounterchar*zData;Partoftherecordbeingdecoded*/ MemsMem;Forstoringtherecordbeingdecoded*/ sMem.flags=0; assert(p1<p->nCursor); 栈顶指针上移 pTos++; pTos->flags=MEM_Null; ThisblocksetsthevariablepayloadSizetobethetotalnumberof **bytesintherecord. ** **zRecissettobethecompletetextoftherecordifitisavailable. **Thecompleterecordtextisalwaysavailableforpseudo-tables **Iftherecordisstoredinacursor,thecompleterecordtext **mightbeavailableinthepC->aRowcache.Oritmightnotbe. **Ifthedataisunavailable,zRecissettoNULL. ** **Wealsocomputethenumberofcolumnsintherecord.Forcursors, **thenumberofcolumnsisstoredintheCursor.nFieldelement.For **recordsonthestack,thenextentrydownonthestackisaninteger **whichisthenumberofrecords. 设置游标 pC=p->apCsr[p1]; assert(pC!=if(pC->pCursor!=TherecordisstoredinaB-Tree移到当前游标 rc=sqlite3VdbeCursorMoveto(pC); if(rc)gotoabort_due_to_error; zRec=0; pCrsr=pC->pCursor; if(pC->nullRow){ payloadSize=0; }elseif(pC->cacheStatus==p->cacheCtr){ payloadSize=pC->payloadSize; zRec=(char*)pC->aRow; }if(pC->isIndex){ i64payloadSize64; sqlite3BtreeKeySize(pCrsr,&payloadSize64); payloadSize=payloadSize64; }else{ 解析数据,payloadSize保存cell的数据字节数 sqlite3BtreeDataSize(pCrsr,&payloadSize); } nField=pC->nField; }if(pC->pseudoTable){ Therecordisthesoleentryofapseudo-table*/ payloadSize=pC->nData; zRec=pC->pData; pC->cacheStatus=CACHE_STALE; assert(payloadSize==0||zRec!=0); nField=pC->nField; pCrsr=else{ zRec=0; payloadSize=0; pCrsr=0; nField=0; } IfpayloadSizeis0,thenjustpushaNULLontothestack.if(payloadSize==0){ assert(pTos->flags==MEM_Null); break; } assert(p2<nField); Readandparsethetableheader.Storetheresultsoftheparse **intotherecordheadercachefieldsofthecursor. if(pC&&pC->cacheStatus==p->cacheCtr){ aType=pC->aType; aOffset=pC->aOffset; }else{ u8*zIdx;Indexintoheader*/ u8*zEndHdr;Pointertofirstbyteaftertheheader(指向header之后的第一个字节)*/ u32offset;OffsetintothedataintszHdrSz;Sizeoftheheadersizefieldatstartofrecordintavail;Numberofbytesofavailabledata*/ 数据类型数组 aType=pC->aType; if(aType==每个数据类型分配8字节---sizeof(aType)==4 pC->aType=aType=sqliteMallocRaw(2*nField*sizeof(aType)); } gotono_mem; } 每列数据的偏移 pC->aOffset=aOffset=&aType[nField]; pC->payloadSize=payloadSize; pC->cacheStatus=p->cacheCtr; Figureouthowmanybytesareintheheaderif(zRec){ zData=zRec; }if(pC->isIndex){ zData=(char*)sqlite3BtreeKeyFetch(pCrsr,&avail); }获取数据 zData=(char*)sqlite3BtreeDataFetch(pCrsr,&avail); } IfKeyFetch()/DataFetch()managedtogettheentirepayload, **savethepayloadinthepC->aRowcache.Thatwillsaveusfrom **havingtomakeadditionalcallstofetchthecontentportionof **therecord. if(avail>=payloadSize){ zRec=zData; pC->aRow=(u8*)zData; }else{ pC->aRow=0; } } assert(zRec!=0||avail>=payloadSize||avail>=9); 获得headersize szHdrSz=GetVarint((u8*)zData,offset); TheKeyFetch()orDataFetch()abovearefastandwillgettheentire **recordheaderinmostcases.Buttheywillfailtogetthecomplete **recordheaderiftherecordheaderdoesnotfitonasinglepage **intheB-Tree.Whenthathappens,usesqlite3VdbeMemFromBtree()to **acquirethecompleteheadertext. if(!zRec&&avail<offset){ rc=sqlite3VdbeMemFromBtree(pCrsr,0,offset,pC->isIndex,&sMem); if(rc!=SQLITE_OK){ gotoop_column_out; } zData=sMem.z; } 一个记录的例子: **08|08|04001301|63617401 **08:nSize,payload总的大小——后面8个字节 **08:关键字大小,对于整型则为关键字本身 **04:headersize,包括本身共4个字节——04001301 **00:第一列的数据类型——空类型 **13:第二列的数据类型——字符串,长为(19-13)/2=3——“cat” **01:第三列的数据类型——整型,占一个字节——1 **对于这里的zData保存的数据为:0400130163617401 header之后的数据,对于上例为:63617401 zEndHdr=(u8*)&zData[offset]; header数据的索引号,对于上例为:001301 zIdx=(u8*)&zData[szHdrSz]; ScantheheaderanduseittofillintheaType[]andaOffset[] **arrays.aType[i]willcontainthetypeintegerforthei-th **columnandaOffset[i]willcontaintheoffsetfromthebeginning **oftherecordtothestartofthedataforthei-thcolumn 扫描header,然后设置aType[]和aOffset[]数组;aType[i]为第i列的数据类型, **aOffset[i]为第i列数据相对于记录的开始的偏移. for(i=0;i<nField;i++){ if(zIdx<zEndHdr){ 计算每一列数据的偏移 aOffset[i]=offset; 计算每一列的数据类型 zIdx+=GetVarint(zIdx,aType[i]); offset指向下一列 offset+=sqlite3VdbeSerialTypeLen(aType[i]); }IfiislessthatnField,thentherearelessfieldsinthis **recordthanSetNumColumnsindicatedtherearecolumnsinthe **table.Settheoffsetforanyextracolumnsnotpresentin **therecordto0.ThistellscodebelowtopushaNULLontothe **stackinsteadofdeserializingavaluefromtherecord. */ aOffset[i]=0; } } Release(&sMem); sMem.flags=MEM_Null; Ifwehavereadmoreheaderdatathanwascontainedintheheader, **oriftheendofthelastfieldappearstobepasttheendofthe **record,thenwemustbedealingwithacorruptdatabase. if(zIdx>zEndHdr||offset>payloadSize){ rc=SQLITE_CORRUPT_BKPT; gotoop_column_out; } } Getthecolumninformation.IfaOffset[p2]isnon-zero,then **deserializethevaluefromtherecord.IfaOffset[p2]iszero, **thentherearenotenoughfieldsintherecordtosatisfythe **request.Inthiscase,setthevalueNULLortoP3ifP3is **apointertoaMemobject. 获取P2指定的列的数据if(aOffset[p2]){ assert(rc==SQLITE_OK); if(zRec){ 取得该列的数据 zData=&zRec[aOffset[p2]]; }else{ len=sqlite3VdbeSerialTypeLen(aType[p2]); rc=sqlite3VdbeMemFromBtree(pCrsr,aOffset[p2],len,0)">解析zData,并将结果保存在pTos中 sqlite3VdbeSerialGet((u8*)zData,aType[p2],pTos); pTos->enc=encoding; }if(pOp->p3type==P3_MEM){ sqlite3VdbeMemShallowCopy(pTos,(Mem*)(pOp->p3),MEM_Static); }else{ pTos->flags=MEM_Null; } } Ifwedynamicallyallocatedspacetoholdthedata(inthe **sqlite3VdbeMemFromBtree()callabove)thentransfercontrolofthat **dynamicallyallocatedspaceovertothepTosstructure. **Thispreventsamemorycopy. if((sMem.flags&MEM_Dyn)!=0){ assert(pTos->flags&MEM_Ephem); assert(pTos->flags&(MEM_Str|MEM_Blob)); assert(pTos->z==sMem.z); assert(sMem.flags&MEM_Term); pTos->flags&=~MEM_Ephem; pTos->flags|=MEM_Dyn|MEM_Term; } pTos->zmightbepointingtosMem.zShort[].Fixthatsothatwe **canabandonsMem*/ rc=sqlite3VdbeMemMakeWriteable(pTos); op_column_out: 4、Next指令 移动游标,使其指向表的下一个记录 caseOP_Prev:caseOP_Next:{*/ Cursor*pC; BtCursor*pCrsr; CHECK_FOR_INTERRUPT; assert(pOp->p1>=0&&pOp->p1<p->nCursor); pC=p->apCsr[pOp->p1]; assert(pC!=intres; if(pC->nullRow){ res=1; }else{ assert(pC->deferredMoveto== rc=pOp->opcode==OP_Next?sqlite3BtreeNext(pCrsr,&res): sqlite3BtreePrevious(pCrsr,&res); pC->nullRow=res; pC->cacheStatus=CACHE_STALE; } if(res==1; sqlite3_search_count++; } }else{ pC->nullRow=1; } pC->rowidIsValid=0; break; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |