データベース実装勉強会で読んだプログラムのメモ
先日、池袋バイナリ勉強会でのデータベース実装勉強会（http://connpass.com/event/13447/）に参加しました。
select * from testをH2で実行する時に通るプログラムを読むという内容でした。
忘れてしまうのはもったいないので、少し読みなおしてメモ。
かなり憶測まじりな所があります。
/** * クエリ(select文)を実行し、result setを返す。 * もしこの文に他のresult setがある場合、これは閉じられるだろう（たとえこの文は失敗するとしても）（訳） */ @Override public ResultSet JdbcStatement.executeQuery(String sql) throws SQLException { try { int id = getNextId(TraceObject.RESULT_SET); // トレース用のresult setのID取得 if (isDebugEnabled()) { debugCodeAssign("ResultSet", TraceObject.RESULT_SET, id, "executeQuery(" + quote(sql) + ")"); } synchronized (session) { checkClosed(); // 接続が閉じているかチェック closeOldResultSet(); // 以前のresult setが開いていたら閉じる sql = JdbcConnection.translateSQL(sql, escapeProcessing); // JDBCエスケープシーケンスを変換する CommandInterface command = conn.prepareCommand(sql, fetchSize); // SQL文をパースする。キャッシュにあればそれを使う ResultInterface result; boolean scrollable = resultSetType != ResultSet.TYPE_FORWARD_ONLY; // result setがnext方向以外に移動できるか boolean updatable = resultSetConcurrency == ResultSet.CONCUR_UPDATABLE; // result setが更新可能か setExecutingStatement(command); // 実行中のSQL文をセットする try { result = command.executeQuery(maxRows, scrollable); // クエリを実行する（下に続く） } finally { setExecutingStatement(null); // 実行中のSQL文のセットを消す } command.close(); // SQL文を閉じる resultSet = new JdbcResultSet(conn, this, result, id, closedByResultSet, scrollable, updatable); // 実行結果を含んだresult setを作成 } return resultSet; } catch (Exception e) { throw logAndConvert(e); } }
/** * クエリを実行して結果を返す。このメソッドは全てを準備してから query(int) を最後に呼ぶ。（訳） */ @Override public ResultInterface Command.executeQuery(int maxrows, boolean scrollable) { startTime = 0; long start = 0; Database database = session.getDatabase(); Object sync = database.isMultiThreaded() ? (Object) session : (Object) database; // マルチスレッドモードか否かで同期の単位を選択 session.waitIfExclusiveModeEnabled(); // 排他モードなら必要に応じて他のセッションを待つ boolean callStop = true; // 最後にstopを呼ぶフラグ boolean writing = !isReadOnly(); // コマンドが書き込みを行うか if (writing) { while (!database.beforeWriting()) { // wait } } synchronized (sync) { session.setCurrentCommand(this); // セッションの現在のコマンドをセット try { while (true) { database.checkPowerOff(); // データベースのパワーオフ確認 try { return query(maxrows); // クエリの実行（下に続く） } catch (DbException e) { ... // 例外処理 } catch (OutOfMemoryError e) { ... // 例外処理 } catch (Throwable e) { ... // 例外処理 } } } catch (DbException e) { ... // 例外処理 } finally { if (callStop) { stop(); // 一時result setを閉じたり、一時ファイルを削除したり、コミットしたりする } if (writing) { database.afterWriting(); } } } }
@Override public ResultInterface CommandContainer.query(int maxrows) { recompileIfRequired(); // 必要ならクエリの再コンパイル setProgress(DatabaseEventListener.STATE_STATEMENT_START); // イベントリスナにクエリの実行開始を通知 start(); // トレース用の開始時間を得る prepared.checkParameters(); // パラメータのエラーチェック ResultInterface result = prepared.query(maxrows); // クエリの実行（下に続く） prepared.trace(startTime, result.getRowCount()); // トレース用処理 setProgress(DatabaseEventListener.STATE_STATEMENT_END); // イベントリスナにクエリの実行終了を通知 return result; }
@Override public LocalResult Query.query(int maxrows) { return query(maxrows, null); }
/** * クエリを実行して、結果をtarget resultに書く。 * * @param limit * 返す行の最大数 * @param target * the target result (nullの場合はresultを返す) * @return the result set (targetがセットされない場合). */ LocalResult Query.query(int limit, ResultTarget target) { fireBeforeSelectTriggers(); // トリガの実行 if (noCache || !session.getDatabase().getOptimizeReuseResults()) { return queryWithoutCache(limit, target); // キャッシュを使わずクエリ実行（下に続く） } Value[] params = getParameterValues(); // パラメータの値を得る long now = session.getDatabase().getModificationDataId(); if (isEverything(ExpressionVisitor.DETERMINISTIC_VISITOR)) { // 最後の結果(lastResult)を再利用できるか if (lastResult != null && !lastResult.isClosed() && limit == lastLimit) { if (sameResultAsLast(session, params, lastParameters, lastEvaluated)) { lastResult = lastResult.createShallowCopy(session); if (lastResult != null) { lastResult.reset(); return lastResult; } } } } lastParameters = params; closeLastResult(); LocalResult r = queryWithoutCache(limit, target); // 再利用できなかったのでキャッシュを使わずクエリ実行（下に続く） lastResult = r; this.lastEvaluated = now; lastLimit = limit; return r; }
@Override protected LocalResult Select.queryWithoutCache(int maxRows, ResultTarget target) { int limitRows = maxRows == 0 ? -1 : maxRows; // 指定最大行数が0なら制限なし(-1) if (limitExpr != null) { // LIMITやTOP等での行数の制限がある場合 Value v = limitExpr.getValue(session); int l = v == ValueNull.INSTANCE ? -1 : v.getInt(); if (limitRows < 0) { limitRows = l; } else if (l >= 0) { limitRows = Math.min(l, limitRows); } } int columnCount = expressions.size(); // 列数 LocalResult result = null; if (target == null || !session.getDatabase().getSettings().optimizeInsertFromSelect) { // 今回の経路だとtargetはNULL(戻り値resultを返すことを意味する) result = createLocalResult(result); // resultがnullの場合、LocalResult作成する関数 } if (sort != null && (!sortUsingIndex || distinct)) { // ORDER BY result = createLocalResult(result); result.setSortOrder(sort); // sort順をセットする } if (distinct && !isDistinctQuery) { // SELECT DISTINCT result = createLocalResult(result); result.setDistinct(); // distinctフラグをセットする } if (randomAccessResult) { // ランダムアクセスを要求する result = createLocalResult(result); result.setRandomAccess(); // random accessフラグをセットする } if (isGroupQuery && !isGroupSortedQuery) { // GROUP BY, HAVING result = createLocalResult(result); } if (limitRows >= 0 || offsetExpr != null) { // Max Rows, LIMIT, TOP, OFFSET result = createLocalResult(result); } topTableFilter.startQuery(session); // SQL文に含まれるテーブルに、セッションを設定 topTableFilter.reset(); // SQL文に含まれるテーブルの位置をリセット boolean exclusive = isForUpdate && !isForUpdateMvcc; // SELECT .. FOR UPDATE 等から排他ロックの必要性 if (isForUpdateMvcc) { // MVCC使用時にSELECT .. FOR UPDATEで、SELECTされた行のみロックする設定か if (isGroupQuery) { throw DbException .getUnsupportedException("FOR UPDATE && GROUP"); } else if (distinct) { throw DbException .getUnsupportedException("FOR UPDATE && DISTINCT"); } else if (isQuickAggregateQuery) { throw DbException .getUnsupportedException("FOR UPDATE && AGGREGATE"); } else if (topTableFilter.getJoin() != null) { throw DbException.getUnsupportedException("FOR UPDATE && JOIN"); } } topTableFilter.lock(session, exclusive, exclusive); // テーブルのロック ResultTarget to = result != null ? result : target; // ここまででresultが作成されていればそれを使う。そうでなければ引数のtargetを使う if (limitRows != 0) { // 返す最大行数が0の場合は、クエリを実行しない if (isQuickAggregateQuery) { // ダイレクトルックアップを使う集計クエリか queryQuick(columnCount, to); } else if (isGroupQuery) { // GROUP BY, HAVING if (isGroupSortedQuery) { // 不明 queryGroupSorted(columnCount, to); } else { queryGroup(columnCount, result); } } else if (isDistinctQuery) { // 不明 queryDistinct(to, limitRows); } else { queryFlat(columnCount, to, limitRows); // 今回のselect文ではここへ来る（下に続く） } } if (offsetExpr != null) { // LIMIT, OFFSET result.setOffset(offsetExpr.getValue(session).getInt()); // オフセット行数をセットする } if (limitRows >= 0) { // 返す行数が無制限でない result.setLimit(limitRows); // 返す行の最大数をセットする } if (result != null) { // resultがある場合 result.done(); // セットされたdistinct, external, sort, offset, limitを適用する if (target != null) { // 引数targetが指定されている場合はresultの内容をtargetに入れて返す while (result.next()) { target.addRow(result.currentRow()); } result.close(); return null; } return result; // targetが無いので戻り値resultを返す } return null; // resultが無いので引数targetで結果を返す }
private void Select.queryFlat(int columnCount, ResultTarget result, long limitRows) { // limitRowsはlong型でなければならない、そうでなければint型オーバーフローする // もしlimitRowsがInteger.MAX_VALUEか、それに近い値の場合に // ここではlimitRowsは0ではない（訳） if (limitRows > 0 && offsetExpr != null) { // 返す行数が制限されていて、オフセット指定がある場合 int offset = offsetExpr.getValue(session).getInt(); if (offset > 0) { limitRows += offset; } } int rowNumber = 0; setCurrentRowNumber(0); // 行のカウントを0に。キャンセルが有れば例外を投げる。128行毎にイベントリスナに現在の行数を通知する ArrayList<Row> forUpdateRows = null; if (isForUpdateMvcc) { // MVCC使用時にSELECT .. FOR UPDATEで、SELECTされた行のみロックする設定か forUpdateRows = New.arrayList(); // ロック指定のための行リスト } int sampleSize = getSampleSizeValue(session); // LIMIT SAMPLE_SIZE while (topTableFilter.next()) { // テーブルの次の行があるか（※ setCurrentRowNumber(rowNumber + 1); // 行のカウントをセット。キャンセルチェック。イベントリスナに通知。 if (condition == null // WHERE句等による条件に、合致する行か || Boolean.TRUE.equals(condition.getBooleanValue(session))) { Value[] row = new Value[columnCount]; for (int i = 0; i < columnCount; i++) { Expression expr = expressions.get(i); row[i] = expr.getValue(session); // 列の値を取得 } if (isForUpdateMvcc) { topTableFilter.lockRowAdd(forUpdateRows); // ロックする行として、現在の行を追加 } result.addRow(row); // クエリ結果に現在の行を追加 rowNumber++; // 出力行のカウントをインクリメント if ((sort == null || sortUsingIndex) && limitRows > 0 && result.getRowCount() >= limitRows) { break; // sortで順番の入れ替えが発生せず、最大行数まで結果を得たら抜ける } if (sampleSize > 0 && rowNumber >= sampleSize) { // 指定されたサンプリング行数を超えたら抜ける break; } } } if (isForUpdateMvcc) { topTableFilter.lockRows(forUpdateRows); // 行のロックをする } }
topTableFilter.next()を追っていくと、がカーソルやページが出てきて難しい
コマンドクラス周辺
- 点線枠部がパースで生成される
数式処理入門に参加したメモ
先日、池袋バイナリ勉強会でのJava数式処理入門(http://connpass.com/event/7368/)に参加しました。
今まで、プログラムで数式を表現したり、数式から計算をしたりということを考えることがあんまりなかったけど、やってみて面白かったです。
Cで実装してみた。
なかなか勉強会の時間では完成できないけど、帰ってCで書いてみた。
全てに変数に割り当てずに、各構造体のメモリを動的に確保/開放するのは途中であきらめた。 色々やってみたけどできなかった。
PDP-11 MUL命令を、8086のアセンブリ言語に変換したメモ
作成中の、PDP-11アセンブリ -> 8086アセンブリ のトランスレーター(https://github.com/kusabanachi/p11trans)で、 MUL命令の変換部分を書いた
PDP-11 MUL命令
mul src, dest
- destがR0,R2,R4(偶数)の場合
- destがR1,R3,R5(奇数)の場合
- dest レジスタ = src * destの下位16bit
- 上位16bitは格納されない
8086 IMUL命令
符号付き乗算命令なので、x86ではIMUL命令が相当する
imul src
大まかな違い
どちらも同じ目的で使われる命令だが、PDP-11のmul命令がsrcとdestの2つのオペランドを指定するのに対して、8086のimul命令はdestがAXレジスタに固定される。
PDP-11のmul命令はdestレジスタの番号が偶数か奇数かで動作が変わるが、8086のimul命令は1パターン。
PDP11 mul --> 8086 imul の変換
PDP11 mulのdest(以下'dest'と表記)の値により、大きく4パターンに場合分けする
レジスタは
* R0 --> AX * R1 --> DX * R2 --> CX * R3 --> SI * R4 --> DI * R5 --> BP * --> BX(余り)
の変換割り当て。
'dest'がR0の場合
imul src ! ちょうどAX(R0)の位置なのでそのまま計算できる xchg ax, dx ! 'dest'+1がDX(R1)なので、8086計算結果の、上位16bitと下位16bitを交換すればOK
'dest'がR1の場合
mov tmp, ax ! tmpという名の領域に元のAXの値を退避 mov ax, 'dest' ! 'dest'の値をAXにコピーする imul src ! AXに'dest'の値が入ったので計算 mov 'dest' ax ! 計算結果の下位16bitを'dest'(R1)に入れる mov ax, tmp ! 元のAXの値を復元
- 8086IMUL命令で計算結果がAXとDXに入る。
- DX(R1)は計算結果の下位16bitが最終的に入るので、元の値は消えて良い
- AX(R0)の値は変化して欲しくないので、退避/復元する
'dest'がR2,R4の場合 (R0以外の偶数レジスタ)
mov tmp, ax ! tmpという名の領域に元のAXの値を退避 mov tmp2, dx ! tmp2という名の領域に元のDXの値を退避 mov ax, 'dest' ! 'dest'の値をAXにコピーする imul src ! AXに'dest'の値が入ったので計算 mov 'dest' dx ! 計算結果の上位16bitを'dest'に入れる mov 'dest+1' ax ! 計算結果の下位16bitを'dest+1'に入れる mov ax, tmp ! 元のAXの値を復元 mov dx, tmp2 ! 元のDXの値を復元
- 計算結果がAXとDXに入るので、AXとDXの元の値の退避/復元をする
計算結果を'dest'と'dest+1'に格納する
元の'dest'と'dest+1'の場所の値は、計算結果で上書きされてどうせ消えるので、AXとDXの退避場所に使ってxchg命令を使うと、命令数を減らせられる
xchg 'dest', ax ! 'dest'の場所に元のAXの値を退避させ、'dest'の値をAXに入れる mov 'dest+1' dx ! 'dest+1'の場所に元のDXの値を退避 imul src ! AXに'dest'の値が入ったので計算 xchg 'dest' dx ! 計算結果の上位16bitを'dest'に入れる。DXには元AXの値。 xchg 'dest+1' ax ! 計算結果の下位16bitを'dest+1'に入れる。AXには元DXの値。 xchg ax, dx ! 元のAXとDXの値が逆になっているので交換する
'dest'がR3,R5の場合 (R1以外の奇数レジスタ)
mov tmp, ax ! tmpという名の領域に元のAXの値を退避 mov tmp2, dx ! tmp2という名の領域に元のDXの値を退避 mov ax, 'dest' ! 'dest'の値をAXにコピーする imul src ! AXに'dest'の値が入ったので計算 mov 'dest' ax ! 計算結果の下位16bitを'dest'に入れる mov ax, tmp ! 元のAXの値を復元 mov dx, tmp2 ! 元のDXの値を復元
1つ上の偶数レジスタの場合と比べて、'dest+1'に値を格納しないという違いのみ
同様にして命令数を減らすと、
mov tmp, dx ! tmpという名の領域に元のDXの値を退避 xchg 'dest', ax ! 'dest'の場所に元のAXの値を退避させ、'dest'の値をAXに入れる imul src ! AXに'dest'の値が入ったので計算 xchg 'dest' ax ! 計算結果の下位16bitを'dest'に入れる。AXには元AXの値。 mov dx, tmp ! 元のDXの値を復元
srcの値に注意
PDP-11のSXT命令を 8086のアセンブリ言語に変換しようとしたメモ
作成中の、PDP-11アセンブリ -> 8086アセンブリ のトランスレーター(https://github.com/kusabanachi/p11trans)で、 SXT命令の変換部分を書いた
SXT命令とは
対応するような命令が8086にないけど、割とシンプルな命令なのですぐ実装できる気がして取りかかった
最初の実装 *1
mov dest, #0 ! オペランドのdestに0を入れておく jns 8f ! SFが立ってなければ、先の'8'ラベルへジャンプ not dest ! 飛ばされなければ(SFが立ってれば)destを反転 -> 0xffff 8: ! 分岐のためのラベル
あまりラベルを使いたくないけど、まぁしょうがないかと *2
実装後、試してみて問題が見つかる
- オペランドにデクリメントのメモリアドレスが指定された場合が問題に
- 8086ではそのようなオペランドの指定がないので、まずレジスタの値を減算してから演算をするように変換していた
- 例えば
sxt -(r3)なら *3
sub si, 2 ! ここの減算でフラグが上書きされる... mov (si), #0 jns 8f ! ここの分岐はsub命令の結果次第 not (si) 8:
- 呼び出し時点のフラグの状態で結果の値が決まる命令なのに、おかしなことに...
考えた代わりの案
- フラグは元の値に戻そう案
movb tmp, ah ! tmpという名の領域にahの値を退避 lahf ! フラグがahにロードされる命令 sub si, 2 ! フラグが上書きされるが sahf ! 元のフラグの状態に戻す movb ah, tmp ! ahの値を復元 mov (si), #0 jns 8f not (si) 8:
- ジャンプ後にデクリメントしよう案
js 8f ! SF立っていたら8までジャンプ ! SF立っていない時のみ来る sub si, 2 mov (si), #0 jmp 9f ! 9までジャンプ 8: ! SF立っている時のみ来る sub si, 2 mov (si), #0xff 9:
- 分岐しなければいいじゃん案
movb tmp, ah ! tmpという名の領域にahの値を退避 lahf ! フラグがahにロードされる命令 rol ax, #1 ! SFのbitが0bit目(一番右の位置に来る) and ax, #1 ! SFのbit以外クリア neg ax ! 2の補数をとる 1 -> 0xffff. 0 -> 0 sub si, 2 mov (si), ax movb ah, tmp ! ahの値を復元
結局は
- インクリメント・デクリメントはlea命令を使うことにした
- lea命令はメモリのアドレスをレジスタにロードする
- lea命令はフラグの変更が起こらない
lea si, -2(si) ! ([si - 2]が指すメモリ、のアドレス) = si - 2 が、siに入る mov (si), #0 jns 8f not (si) 8:
mov bx, ax ! メモリ参照ができないのでbxにコピー lea ax, -2(bx) ! ([bx - 2]が指すメモリ、のアドレス) = bx - 2 が、axに入る mov bx, ax mov (bx), #0 jns 8f not (bx) 8:
