図面 (/)

技術 メモリリーク箇所の特定方法及び装置

出願人 株式会社日立製作所
発明者 太田智也西山博泰
出願日 2008年3月11日 (13年5ヶ月経過) 出願番号 2008-061513
公開日 2009年9月24日 (11年11ヶ月経過) 公開番号 2009-217617
状態 未査定
技術分野 デバッグ/監視
主要キーワード 割当て位置 箇所特定装置 アルゴリズム適用 割当回数 繰返し動作 トレース範囲 割当位置 トレース状態
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2009年9月24日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (16)

課題

メモリリークが発生する原因を特定する。

解決手段

プログラムの繰返し実行に伴うメモリ割当て及び解放監視し、メモリ割当位置メモリ解放位置とを記録し、メモリ割当位置に対応して割当てたメモリにメモリリークが発生しているか否かを判定し、メモリリークが発生していると判定されたメモリ割当位置に対応して、プログラムの実行に伴い呼び出される関数を複数回トレースし、メモリが解放されるトレース結果とメモリが解放されないトレース結果との差分として得られる関数をメモリリークの発生の原因となる関数であると特定する。

概要

背景

オペレーティングシステム(以下、OS)上で実行されるアプリケーションプログラムは、OSのメモリ管理機能を利用して、プログラムの実行中に必要となるメモリ領域(以下、単にメモリと呼ぶ。)を確保する。一般に、確保したメモリは、不要になると解放される。しかし、プログラムのバグなどにより、確保されたメモリが、不要であるにも関わらず解放されないことがある。このような不良現象は一般に、メモリリークと呼ばれている。

連続稼働(繰返し動作)するアプリケーションプログラムにおいて、メモリリークが繰り返し発生した場合、アプリケーションプログラムの使用するメモリ領域が時間と共に増加する。このような現象長期間放置すると、メモリ不足により、アプリケーションプログラムの実行が継続できなくなる恐れがある。また、アプリケーションプログラムの実行の継続が可能であっても、OSや他のアプリケーションが利用できるメモリ量が減少することにより、システム全体の効率に深刻な影響を与える可能性がある。

このような背景のもと、プログラムの実行時にメモリリークの検出を行う技術が、特許文献1に開示されている。特許文献2に開示されている手法では、プログラムにおけるメモリ割当モジュールの動作を監視することにより、解放漏れが起こっているメモリ領域とその領域を割当てた割当位置(スタックトレース)が取得できる。非特許文献1に開示されている手法では、メモリ割当モジュールの動作を監視することに加えて、メモリ領域の参照を特定の頻度で監視する。。このため、メモリリークを起こしているメモリ領域の割当位置に加えて、最終の参照位置時間情報も併せて取得できる。

特開2001-331368
特開2000-293400
Trishul M. Chilimbi, Matthias Hauswirth:”Low-Overhead Memory Leak Detection Using Adaptive Statistical Profiling”,ASPLOS'04, 2004.

概要

メモリリークが発生する原因を特定する。プログラムの繰返し実行に伴うメモリの割当て及び解放を監視し、メモリ割当位置メモリ解放位置とを記録し、メモリ割当位置に対応して割当てたメモリにメモリリークが発生しているか否かを判定し、メモリリークが発生していると判定されたメモリ割当位置に対応して、プログラムの実行に伴い呼び出される関数を複数回トレースし、メモリが解放されるトレース結果とメモリが解放されないトレース結果との差分として得られる関数をメモリリークの発生の原因となる関数であると特定する。

目的

本発明は、このような従来の問題点に着目し、メモリリークの原因を究明するための情報を取得するメモリリーク箇所検出方法を提供することを目的とする。

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

プログラムの繰返し実行に伴うメモリ割当て及び前記メモリの解放監視し、前記プログラムにおける前記メモリの割当位置と前記メモリの解放位置とを記録し、前記メモリ割当位置に対応して、前記割当てた前記メモリにメモリリークが発生しているか否かを判定し、前記判定の結果、メモリリークが発生していると判定された前記メモリ割当位置に対応して、前記プログラムの実行に伴い呼び出される関数を複数回トレースし、前記複数回のトレース結果の中で前記メモリが解放されるトレース結果と前記メモリが解放されないトレース結果との差分として得られる関数を前記メモリリークの発生の原因となる関数であると特定することを特徴とするメモリリーク箇所特定方法

請求項2

請求項1記載のメモリリーク箇所特定方法において、前記メモリの割当位置に対応して、前記メモリの少なくとも一つの解放位置が記録されているときに、前記メモリリークが発生しているか否かを判定することを特徴とするメモリリーク箇所特定方法。

請求項3

請求項2記載のメモリリーク箇所特定方法において、前記トレースの範囲の終了点を、前記メモリ割当位置と前記メモリ解放位置とを含む関数の出口とすることを特徴とするメモリリーク箇所特定方法。

請求項4

請求項2記載のメモリリーク箇所特定方法において、前記特定した関数を前記メモリの割当位置と対応付けて出力することを特徴とするメモリリーク箇所特定方法。

請求項5

請求項2記載のメモリリーク箇所特定方法において、さらに、メモリリークが発生していると判定された前記メモリ割当位置に対応して、前記プログラムの実行に伴う分岐命令を複数回トレースし、前記複数回のトレース結果の中で前記メモリが解放されるトレース結果と前記メモリが解放されないトレース結果との差分として得られる分岐命令を前記メモリリークの発生の原因となる分岐命令であると特定することを特徴とするメモリリーク箇所特定方法。

請求項6

請求項5記載のメモリリーク箇所特定方法において、前記分岐命令のトレースを、前記特定された関数に関して実行することを特徴とするメモリリーク箇所特定方法。

請求項7

請求項5記載のメモリリーク箇所特定方法において、前記特定した分岐命令を前記メモリの割当位置と対応付けて出力することを特徴とするメモリリーク箇所特定方法。

請求項8

プログラムの実行に伴ったメモリリークの検出に応答して、前記メモリリークを検出したメモリを割当てたメモリ割当位置に対応して、前記プログラムの繰返し実行で呼び出される関数を複数回トレースする関数トレース部、前記関数トレース部による前記複数回のトレース結果の中で前記メモリが解放される関数経路情報と前記メモリが解放されない関数経路情報とを生成する関数経路情報生成部、及び前記生成された前記メモリが解放される関数経路情報と前記メモリが解放されない関数経路情報との差分として得られる関数を前記メモリリークの発生の原因となる関数であると特定する関数特定部を有することを特徴とするメモリリーク箇所特定装置

請求項9

請求項8記載のメモリリーク箇所特定装置において、さらに、前記プログラムの繰返し実行に伴う前記メモリの割当て及び前記メモリの解放を監視し、前記プログラムにおける前記メモリ割当位置と前記メモリのメモリ解放位置とを記録するメモリ割当情報収集部、及び前記メモリ割当情報収集部により記録された前記メモリ割当位置に対応して、前記割当てた前記メモリの前記メモリリークを検出するメモリリーク検出部を有することを特徴とするメモリリーク箇所特定装置。

請求項10

請求項9記載のメモリリーク箇所特定装置において、前記メモリ割当情報収集部により記録された前記メモリ割当位置に対応して前記メモリ解放位置が一つも記録されていないときに、前記メモリリーク検出部は前記メモリリークを検出しないことを特徴とするメモリリーク箇所特定装置。

請求項11

請求項10記載のメモリリーク箇所特定装置において、前記関数トレース部による前記トレースの範囲の終了点を、前記メモリ割当位置と前記メモリ解放位置とを含む関数の出口とすることを特徴とするメモリリーク箇所特定装置。

請求項12

請求項10記載のメモリリーク箇所特定装置において、前記関数特定部が特定した関数を前記メモリの割当位置と対応付けて出力する出力部を有することを特徴とするメモリリーク箇所特定装置。

請求項13

請求項10記載のメモリリーク箇所特定装置において、さらに、前記メモリリークが発生していると判定された前記メモリ割当位置に対応して、前記プログラムの実行に伴う分岐命令を複数回トレースする分岐トレース部、前記分岐トレース部による前記複数回のトレース結果の中で前記メモリが解放される分岐経路情報と前記メモリが解放されない分岐経路情報とを生成する分岐経路情報生成部、及び前記生成された前記メモリが解放される分岐経路情報と前記メモリが解放されない分岐経路情報との差分として得られる分岐命令を前記メモリリークの発生の原因となる分岐命令であると特定する分岐特定部を有することを特徴とするメモリリーク箇所特定装置。

請求項14

請求項13記載のメモリリーク箇所特定装置において、前記分岐トレース部は前記分岐命令のトレースを、前記関数特定部によって特定された関数に関して実行することを特徴とするメモリリーク箇所特定装置。

請求項15

請求項13記載のメモリリーク箇所特定装置において、前記分岐特定部により特定された前記分岐命令を前記メモリの割当位置と対応付けて出力する出力部を有することを特徴とするメモリリーク箇所特定装置。

技術分野

0001

本発明は、プログラム実行時のメモリリークの検出に対応して、そのメモリリーク箇所(発生要因)の特定技術に関する。

背景技術

0002

オペレーティングシステム(以下、OS)上で実行されるアプリケーションプログラムは、OSのメモリ管理機能を利用して、プログラムの実行中に必要となるメモリ領域(以下、単にメモリと呼ぶ。)を確保する。一般に、確保したメモリは、不要になると解放される。しかし、プログラムのバグなどにより、確保されたメモリが、不要であるにも関わらず解放されないことがある。このような不良現象は一般に、メモリリークと呼ばれている。

0003

連続稼働(繰返し動作)するアプリケーションプログラムにおいて、メモリリークが繰り返し発生した場合、アプリケーションプログラムの使用するメモリ領域が時間と共に増加する。このような現象長期間放置すると、メモリ不足により、アプリケーションプログラムの実行が継続できなくなる恐れがある。また、アプリケーションプログラムの実行の継続が可能であっても、OSや他のアプリケーションが利用できるメモリ量が減少することにより、システム全体の効率に深刻な影響を与える可能性がある。

0004

このような背景のもと、プログラムの実行時にメモリリークの検出を行う技術が、特許文献1に開示されている。特許文献2に開示されている手法では、プログラムにおけるメモリ割当モジュールの動作を監視することにより、解放漏れが起こっているメモリ領域とその領域を割当てた割当位置(スタックトレース)が取得できる。非特許文献1に開示されている手法では、メモリ割当モジュールの動作を監視することに加えて、メモリ領域の参照を特定の頻度で監視する。。このため、メモリリークを起こしているメモリ領域の割当位置に加えて、最終の参照位置時間情報も併せて取得できる。

0005

特開2001-331368
特開2000-293400
Trishul M. Chilimbi, Matthias Hauswirth:”Low-Overhead Memory Leak Detection Using Adaptive Statistical Profiling”,ASPLOS'04, 2004.

発明が解決しようとする課題

0006

特許文献1に開示される技術では、メモリリークの検出は可能であるが、プログラムを修正する作業時に必要な情報は得られず、別途メモリリーク状態を再現させて原因を特定する必要がある。

0007

特許文献2に開示の技術は、メモリリークが発生しているメモリの割当位置を特定できる。しかし、メモリ割当位置の情報から、メモリが解放されない原因を特定することは困難である。非特許文献1に開示の技術では、最後のメモリ参照位置が特定できるため、得られた情報によっては、調査する範囲をある程度絞り込める可能があるが、効果は限定的である。

0008

本発明は、このような従来の問題点に着目し、メモリリークの原因を究明するための情報を取得するメモリリーク箇所検出方法を提供することを目的とする。

課題を解決するための手段

0009

本発明のメモリリーク箇所特定方法及びその装置は、プログラムの繰返し実行に伴うメモリの割当て及び解放を監視し、メモリ割当位置とメモリ解放位置とを記録し、メモリ割当位置に対応して割当てたメモリにメモリリークが発生しているか否かを判定し、メモリリークが発生していると判定されたメモリ割当位置に対応して、プログラムの実行に伴い呼び出される関数を複数回トレースし、メモリが解放されるトレース結果とメモリが解放されないトレース結果との差分として得られる関数をメモリリークの発生の原因となる関数であると特定する。

0010

本発明の望ましい態様は、メモリの割当位置に対応して、メモリの少なくとも一つの解放位置が記録されているときに、メモリリークが発生しているか否かを判定する。

0011

本発明の望ましい他の態様は、トレースの範囲の終了点を、メモリ割当位置とメモリ解放位置とを含む関数の出口とする。

0012

本発明の望ましい他の態様は、さらに、メモリリークが発生していると判定されたメモリ割当位置に対応して、プログラムの実行に伴う分岐命令を複数回トレースし、メモリが解放されるトレース結果とメモリが解放されないトレース結果との差分として得られる分岐命令をメモリリークの発生の原因となる分岐命令であると特定する。

発明の効果

0013

プログラムの実行時に、メモリリークを起こしているメモリ割当位置に対して、メモリリークの原因となっている関数及び/又は分岐命令を特定できる。

発明を実施するための最良の形態

0014

以下、本発明の実施形態を、図面を用いて説明する。なお、以下の説明により、本発明の適用が限定されるものではない。

0015

本実施形態を実現する計算機ハードウェア構成図2に示す。計算機は、CPU201、主記憶装置202、ディスク装置外部記憶装置)203を構成要素に含み、それらはバス204で接続されている。本実施形態のメモリリーク箇所特定は、主記憶装置202、もしくは、ディスク装置203に格納され、CPU201で実行されるプログラムの処理により実現される。なお、計算機には、図示しない入力装置出力装置通信装置などが接続されていてもよい。

0016

図1は、メモリリークが生じている可能性がある対象プログラムと、メモリリーク箇所特定のための制御プログラム及びデータ(種々の情報テーブル等)のソフトウエア構成である。ラッパルーチン104、バイナリ書換部103、関数トレース出力部102は、対象プログラム101と同じプロセスで動作する。

0017

ラッパルーチン104は、対象プログラム101で実行されるメモリ操作メモリ割当て、メモリ解放)モジュールの実行を横取りし、本来のメモリ操作モジュールの呼び出しに加えて、メモリ操作に関する情報を、共有メモリ105上に確保されたメモリ管理情報107に記録する。実行の横取りには、ダイナミックリンクリンカプリロード機能を利用する。

0018

バイナリ書換部103は、対象プログラム101を主記憶装置202にロードする時に、対象プログラム101に関数トレース出力部102を埋め込む。関数トレース出力部102は、対象プログラム101の実行に伴う関数の入口と出口でログ情報を関数トレースバッファ106に記録する。なお、ログ情報は、図示していない共有メモリ上のトレース制御フラグがオンのとき出力され、オフのとき出力されない。プログラムロード時のバイナリ書換方法(関数トレース出力部102の埋め込み方法)は非特許文献(Yasushi Saito:”Jocky:A User-space Library for Record-replay Debugging”, AADEBUG'05, 2005.)に開示されている。

0019

制御部109は、対象プログラム101とは異なるプロセスで動作する。したがって、共有メモリ105とは、異なるプロセスで動作する対象プログラム101と制御部109とが共有するメモリ領域を意味する。メモリ管理情報監視部110は、メモリ管理情報107を調べ、メモリリークの発生の有無を調べる。関数経路情報取得部111は、関数トレース出力部102を制御する(トレース制御フラグをオンする)ことで関数トレース情報を取得し、結果を関数経路情報として記録する。分岐経路情報取得部112は、分岐トレース情報を取得し、取得した結果を分岐トレースバッファ113に分岐経路情報として記録する。関数経路情報及び分岐経路情報については後述する。

0020

関数トレースの取得の制御や分岐トレースの取得では、対象プログラム101の実行がトレース範囲終了位置に達したことを、デバッガブレイクポイントと同じ方式にて特定する。そのため、ブレイクポイントに関する情報を共有メモリ105上のブレイクポイント情報108で管理する。また、制御部109は、ptraceシステムコールなどのOS115が提供するデバッガ向けインタフェースを利用することで、対象プログラム101でのブレイクポイントトラップの発生を監視する。出力部114は、メモリ管理情報107に記録されている結果を、プログラム終了時、あるいは、ユーザからの要求に応じて出力する。

0021

図3(a) (b)及び(c)に、ラッパルーチン104及び制御部109によるメモリリーク箇所特定処理フローチャートを示す。図3(a)のステップ305がラッパルーチン104の処理、図3(b)のステップ310〜315が主としてメモリ管理情報監視部110の処理、図3(c)のステップ320〜335が主として関数経路情報取得部111の処理、及びステップ335〜355が主として分岐経路情報取得部112の処理である。なお、本実施形態では各処理の起動タイミング差異を明らかにするために図3(a) (b)及び(c)に分けて図示及び説明するが、処理内容が同じであれば(同様の結果が得られれば)、各処理の構造や起動タイミングは本実施形態にとらわれない。

0022

対象プログラム101の実行が開始されると、ラッパルーチン104により、対象プログラム101のメモリの割当位置と解放位置との対応付け、及び、メモリ割当位地毎のメモリ割当情報がメモリ管理情報107に記録され(ステップ305)、対象プログラム101の実行の終了に伴ってメモリ割当情報の収集を終了する。メモリ管理情報107は、図4(a)に示すブロック管理テーブル401と、図4(b)に示す割当管理テーブル410を含む。

0023

対象プログラム101でメモリの割当が実行されると、ラッパルーチン104は、ブロック管理テーブル401に新たなエントリを確保し、割当てたメモリのアドレス402及びサイズ403欄に割当てたメモリのアドレス及びサイズを記録する。また、割当位置(スタックトレース)を取得する。割当位置は対象プログラム101の中でメモリ操作(メモリ割当て)モジュールを実行する位置であり、スタックに格納された関数呼び出しリターンアドレスから得られる関数を示す。新たな割当位置ごとに割当管理テーブル410にエントリを確保し、ID欄411、割当位置欄412を設定し、割当回数欄414に1を設定する。既に割当管理テーブル410にエントリが確保されている割当位置でのメモリ割当て(同じ割当て位置での2回目以降のメモリ割当て)の場合は、新たなエントリを確保せずに、割当回数欄414を更新する(+1する)。なお、図示しないが、ブロック管理テーブル401のエントリと、割当管理テーブル410のエントリの対応関係を保持する欄もそれぞれのテーブルは含んでいる。

0024

割当位置は対象プログラム101の中でメモリ操作(メモリ解放)モジュールが実行された場合は、メモリ解放されるメモリアドレスからブロック管理テーブル401のエントリ及び割当管理テーブル410のエントリを特定し、解放位置リスト413に解放位置を格納し、解放回数415を更新し(+1し)、特定したブロック管理テーブル401のエントリを削除する。なお、ブロック管理テーブル401及び割当管理テーブル410については後述する。

0025

次にメモリリーク発生の有無を判定する(ステップ310)。タイマ等により一定時間間隔起動され、割当管理テーブル410をスキャンして、メモリリーク発生の有無を判定する。ステップ310のメモリリーク検出処理のフローチャートを図5に示す。判定処理では、メモリ解放回数が1回以上(ステップ500)、かつ、指標値のすべてが基準値以上(ステップ505,510)の場合に、リークありと判定(ステップ515)し、これらの条件を満たさない場合、リークなしと判定(ステップ520)する。対象プログラム101の開始直後にメモリを確保し、終了直前で解放されるメモリは、メモリリーク発生の確率が低いので除外し、実行の途中で(詳しくは、後述するようにトレース反内で)1回以上メモリ解放されているメモリを対象にメモリリーク箇所を特定するためである。

0026

ステップ500で判定したメモリ解放回数が1回以上であることが必要最小限の指標値であり、ステップ505,510で判定する指標値は無くても良いが、メモリ割当量、メモリ割当回数の他、特許文献1や、非特許文献1で開示されている手法で用いられる指標、あるいは、それらの組み合わせを用いる。ステップ310においてメモリリークありと判定されたメモリ割当位置に対しては、割当管理テーブル410の状態欄417を”関数トレース”に更新し、関数/分岐トレース取得処理を起動する(ステップ315)。これにより、次のこの割当位置における次のメモリ確保処理の実行時点から、ステップ320からステップ335によるメモリリークの原因関数の特定処理及びステップ340からステップ355による分岐の特定処理を実行する。

0027

関数トレース取得処理320では、基本的にメモリ割当て処理が実行された位置から、解放処理が実行された位置までの関数トレース(呼び出された関数とその出入口のトレース)を取得する。しかし、対象プログラム101がメモリリークを起こしていると、メモリの解放処理が実行されない。そのため、メモリの解放以外におけるトレースの終了点を定める。トレースの終了点は、割当管理テーブル410の割当位置412と、解放位置リスト413に記録されたスタックトレースに現れる最下位共通関数の出口とする。このようにして関数のトレース範囲を定め、定めたトレース範囲において関数トレースを複数回(繰返し)実行する。繰返し回数は、トレース結果がプログラムのすべての実行経路網羅できる回数が望ましいが、プログラムが複雑であれば複雑であるほど困難である。そこでプログラムの複雑さに応じて繰返し回数を定めることが望ましい。

0028

図6に示す疑似コードを対象プログラム101の例として説明する。図中の関数funcA(601)では、関数malloc(602)によりメモリが割当てられる。その後の実行経路は次の3通りがある。
経路1:エラー条件1(603)が成立して、メモリの解放漏れとなる。
経路2:エラー条件2(605)が成立して、メモリ解放される。
経路3:エラー条件1(603)、エラー条件2(605)とも成立せず、関数funcBの最後の関数free(604)に到達してメモリ解放される。
なお、図中のlocation1、location2は、その行のif文における分岐命令のアドレスを表す記号である。

0029

関数トレース取得処理320の実行までに、図6に示す疑似コードのすべての経路が実行された場合、割当管理テーブル410の割当位置欄412には、次が記録されている。
funcA(), malloc()
また、解放位置リスト欄413には、次の2つが記録されている。
funcA(), funcB(), sub1(), free()
funcA(), funcB(), free()
これら3つのスタックトレースの最下位の共通関数(最も早くスタックされた共通関数)は、関数funcAであるので、割当管理テーブル410の範囲終了点欄416に、関数funcAを格納する。

0030

関数トレース情報の取得は、メモリ割当てを実行するラッパルーチン、メモリ解放を実行するラッパルーチン、及び、ブレイクポイントとそのハンドラよって行う。なお、ブレイクポイントの設定方法及びブレイクポイント到達時の処理の制御に関しては、既存のデバッガの技術を利用する。

0031

図7にそれぞれの箇所で、関数トレース取得時に適用される関数トレース取得処理のフローチャートを示す。図7(a)は、メモリ割当を実行するラッパルーチンにおける処理である。割当管理テーブル410の該当するエントリの状態欄417から関数トレース状態か否かを調べる(ステップ701)。関数トレース状態の場合、ブロック管理テーブル401の開始ID欄404に関数トレースバッファ106の最終位置最新関数トレースデータを格納している、関数トレースバッファ106のエントリのID)を記録する。また、範囲終了点欄416に記録されている関数の出口にブレイクポイントが設定されていない場合、ブレイクポイントを設定し、その情報を割当管理テーブル410のID411欄の値と関連付けてブレイクポイント管理情報108に記録する。最後に、関数トレースの出力を制御するトレース制御フラグを設定して関数トレースが出力される状態にする(ステップ702)。

0032

次に、このメモリブロックが解放される場合の処理を、図7(b)に示す。まず、関数トレース状態か否かを調べる(ステップ710)。関数トレース状態なら、ブロック管理テーブル401の終了ID欄405を調べる(ステップ711)。この欄が空の場合、関数トレースバッファ106の最終位置(最新の関数トレースデータを格納している、関数トレースバッファ106のエントリのID)を終了ID欄405に記録し関数経路情報生成処理を呼ぶ(ステップ713)。この欄が空でない場合は、既に解放処理の到達前に、トレース範囲の終了点に到達していることを意味する。その場合、範囲終了点欄416に記録されている関数をスタック上の一つ上位の関数に更新し、関数経路情報欄418を空にする(ステップ712)。これにより、以降のメモリ割当の実行時には、新たな範囲での経路情報の収集が行われる。

0033

次に、プログラムの実行がトレース範囲の終了点に到達した場合、ブレイクポイントトラップが発生する。トラップに対する処理を図7(c)に示す。まず、関数トレース状態か否かを調べる(ステップ720)。関数トレース状態なら、ブレイクポイント管理情報108を調べて、トラップが発生したアドレスがトレース範囲の終了点となっている割当管理テーブル410のエントリを見つけ、さらに、それらのエントリに対応するブロック管理テーブル401のエントリをすべて見つける(ステップ721、722)。そして見つけたそれぞれのエントリに対して、終了ID欄405に関数トレースバッファ106の最終位置(最新の関数トレースデータを格納している、関数トレースバッファ106のエントリのID)を記録し、関数経路情報生成処理を呼ぶ(ステップ723)。以上の処理により、関数トレース取得状態にあるメモリ割り当て点の1回の実行における関数トレースが取得される。

0034

図8に関数トレース取得例を示す。図6の疑似コードにおいて、関数malloc(602)によりメモリが割当られ、関数free(604)の到達する経路を通った場合に作成される関数トレースバッファの内容を図8(a)に、その時のブロック管理テーブルの状態を図8(b)に示す。関数トレースバッファ801には、エントリを一意に表すID欄802、関数欄803、入口か出口かを示す種別欄804が含まれる。図8(b)では、所定のエントリ811の開始ID欄にメモリ割当が実行された時点での関数トレースバッファ801の最終IDである100、終了ID欄809にメモリ解放命令が実行された時点での関数トレースバッファ801の最終IDである107が記録される。

0035

関数経路情報生成処理325では、以上の処理により取得された1回分トレース情報を入力として、それまでに入力されたトレース情報を統合した関数経路情報を作成する。関数経路情報は、割当管理テーブル410のエントリごとに作成し、関数経路情報欄418に記録する。関数経路情報の生成は、sequiturアルゴリズム(Nevill-Manning,C.G,Witten.I.H,”Identifying Hierarchical Structure in Sequences:A linear-time algorithm”, Journal of Artificail Intelligence Research,pp67-82,1997)を利用する。すなわち、関数経路情報は、sequiturアルゴリズムにより導出される生成規則集合として表現する。

0036

図9に関数経路情報生成処理のフローチャートを示す。まず、入力となる1つの関数トレース全体を表現する新たなシンボル'S'を導入する(ステップ901)。次に関数トレースバッファの開始IDから終了IDまでのエントリを関数欄と種別欄の組をシンボルとして、sequiturアルゴリズムを適用する(ステップ902)。ステップ902においては、それまでの関数経路情報の構築時に利用されたdigram(sequiturアルゴリズム適用時に生成される内部データ)も利用する。ステップ902の適用後、最後の入力シンボルとして、関数経路情報生成処理325がメモリ解放モジュールから呼び出されているなら、メモリ解放が実行されたことを示すシンボル'F'を、そうでないならメモリ解放が行われていなことを示すシンボル'E'を入力とする(ステップ903,904,905)。以上の処理の結果、シンボル'S'の右辺が1つのシンボルで表現された場合、今回とまったく同じ関数トレースが以前にも入力されていたことを示す。そのため、右辺が1つのシンボルの場合、シンボル'S'に関する規則を取り除く。そうでない場合、シンボル'S'に関するルールを関数経路情報に追加する(ステップ906、907、908)。

0037

図10に関数経路情報生成の例を示す。図10(a)は、図8に示す関数トレースに対して関数経路情報生成処理を適用した結果である。生成規則S1(1001)がトレース全体を表現している。尚、図中では、シンボルを、対応するエントリの関数名に種別がstartの場合はSを、種別がexitの場合はEを、ハイフンで繋げた形式で表現している。

0038

次に、図6擬似コードにおいて、エラー条件2(605)が成立する経路が実行された場合の関数トレースバッファ(1010)と、それが入力されたことにより生成される関数経路情報(1011)を図10(b)に示す。この場合、入力は、ID欄が200から201までの間とする。このトレースを表すシンボルは、'S2'であり、S1と共通する経路情報は、シンボル'N1'が導入され、圧縮されて記録されている。次に同様にして、図6の擬似コードにおいて、エラー条件1(603)が成立する経路が実行された場合の関数バッファ(1020)と、生成される関数経路情報(1021)を図10(c)に示す。関数経路情報生成処理により、新たなルールS3が追加され、他の経路と共通する経路情報は、非終端記号N2が導入され、圧縮されていることが分かる。

0039

関数経路情報生成処理325が適用される度に、関数経路情報収集終了判定処理330が適用される。終了判定の基準は、現在処理対象となっている割当管理テーブル410のエントリにおいて、関数トレース状態になったのち、解放位置リスト欄413に登録されているすべての解放位置の実行、及び、メモリ解放漏れ実行経路が少なくとも1回は実行された場合とする。これは、関数トレース取得状態になったのちの、割付情報管理テーブル410の解放位置リスト欄413に登録されている解放位置の到達の有無と範囲終了点到達の有無を記録すれば判定可能である。なお、この判定処理において、関数経路情報の収集が終了と判定された場合、他に関数トレース状態の割当管理テーブル410のエントリがないか調べる。もし、存在しない場合、関数トレース制御フラグにより関数トレースの出力を終了させる。これにより、関数トレースは必要な場合にのみ出力するように制御できる。

0040

関数特定処理335では、関数経路情報から、メモリが解放される経路と解放されない経路との差分を求めることで、メモリリークの原因がある関数を特定する。図11に関数特定処理のフローチャートを示す。まず、関数経路情報に含まれる経路情報のうち、メモリ解放が実行されない経路のそれぞれに対して(ステップ1101)、その経路情報を最終位置の直前事象(つまり、最後のシンボル'F'または、'E'を除く)から前方向に、メモリが解放される経路に含まれる事象(関数の呼び出し、もしくは、終わり)に到達するかを調べる(ステップ1102〜1105)。なお、このとき、メモリが解放される経路の最後の事象を特定するため、メモリが解放される経路を最後のシンボルから前方向に検索を行う。もし、事象が特定できた場合、その事象が発生した関数を、経路情報をさらに前方に辿ることで特定し、結果リストに特定した関数を追加する(ステップ1106)。以上の処理により、結果リストには、メモリ解放が行われた実行経路と、メモリ解放が行われなかった実行経路との違いが発生する関数が特定される。特定された結果を、対応する割当管理テーブル410のエントリの関数リスト欄419に記録する。

0041

例えば、図10(c)の関数経路情報1021の場合、メモリが解放されない経路は、S3である。S3において、シンボル'E'の直前のシンボルは、'sub2-E'である。これは、経路S1において、シンボル'F'の直前に見つかる。関数sub2の呼び出し終了の事象が起こっているのは、関数と種別の情報を元に、さらに経路を遡ることで、関数funcBであることが特定できる。これにより、図11の処理により、メモリリークが発生する原因は、関数funcBであることが特定できる。特定した関数を、要求に応じて、割当てたメモリやその割当位置と対応付けて出力する。

0042

関数特定処理335でメモリリークが発生する関数が特定されると、次に、分岐トレースの取得を行う(ステップ340)。分岐トレースは割当管理テーブル410の状態欄417に分岐トレース状態であることを記録することにより開始される。分岐トレースの取得制御は、トレースそのものを取得する方法は異なるが、制御は関数トレースの取得と同様に、メモリ割当のラッパルーチン、メモリ解放のラッパルーチン、及び、ブレイクポイントとそのハンドラよって行う。

0043

図12にそれぞれの箇所で、分岐トレース取得時に適用される分岐トレース取得処理のフローチャートを示す。割当管理テーブル410の状態が分岐トレースの場合にメモリ割当のラッパルーチンで追加実行される処理を、図12(a)に示す。まず、割当管理テーブル410の該当するエントリの状態欄417から分岐トレース状態か否かを調べる(ステップ1201)。分岐トレースバッファ113の最終位置を、対応するブロック管理テーブル401のエントリの開始ID欄404に記録する。次に、割当管理テーブル410の対応するエントリの関数リスト419欄に登録されている関数にブレイクポイントを設定し、その情報を、割当管理テーブル410のIDと関連付けて、ブレイクポイント管理テーブル108に記録する(ステップ1202)。対象プログラム101の実行中にトラップが発生した場合、ブレイクポイント管理テーブル108により、そのトラップが分岐トレース対象関数の開始であるのかを判定し、分岐トレース対象関数の開始である場合、OSのデバッガ用のインタフェースが提供している機能を用いて、ブロックステッピングを行い、対象関数中で実行される分岐命令のアドレス等を分岐トレースバッファ113に記録する。対象関数とは、割当管理テーブル410の対応するエントリの関数リスト419欄に登録されている関数である。

0044

分岐トレースバッファ113の構成例を図13に示す。分岐トレースバッファ113は、ID欄1302、関数欄1303、スタックの深さ欄1304、分岐命令のアドレス欄1305を含む。なお、分岐トレースには、関数の開始情報も含める。関数の開始情報の場合、関数欄1303とスタックの深さ欄1304に情報が記録される。分岐命令のログの場合、アドレス欄1305にのみ情報(分岐先アドレス)が記録される。

0045

図12(b)に、メモリ解放のラッパルーチンで実行される処理を示す。割当管理テーブル410の該当するエントリの状態欄417から分岐トレース状態か否かを調べる(ステップ1210)。ブロック管理テーブル401のIDが空の場合、分岐トレースバッファ113の最終位置(最新の分岐トレースデータを格納している、分岐トレースバッファ113のエントリのID)を記録して、分岐経路情報生成処理345を呼び出す(ステップ1211、1213)。ブロック管理テーブル401のIDが空でない場合、トレース範囲終了点欄416にスタックトレースの一段上の関数を記録し、関数経路情報欄418と、関数リスト欄419、分岐経路情報欄420をクリアして、状態欄417を関数トレース取得状態へ戻す(ステップ1211、1212)。この場合は図3において、ステップ320に戻るが、図示を省略している。

0046

図12(c)は、プログラムの実行がトレース範囲の終了点に到達した場合に発生するトラップに対する処理である。関数トレース情報取得時との違いは、ステップ1223において、終了IDとして分岐トレースバッファの最終位置を記録し、分岐経路情報生成処理345を呼び出すことである。ステップ1220〜1222は、関数トレース情報取得時の図7(c)のステップ720〜722と同様であるので、説明を省略する。

0047

分岐経路情報生成処理345では、分岐トレースの結果を元に、分岐経路情報を生成する。分岐経路生成情報は、割当管理テーブル410のエントリごとに、かつ、関数リスト欄418に登録されている関数ごとに生成される。生成された分岐経路情報は割当管理テーブル410の分岐経路情報リスト欄420に関数リスト欄419の関数に対応付けて記録する。

0048

図14に分岐経路生成処理345のフローチャートを示す。関数トレースの場合と異なり、入力となる分岐トレースバッファ113の内容は、対象とする割当位置には関係のないログ情報が含まれていたり、関係する関数でも複数回実行されていたりする。そのため、まず、分岐トレースの内容を、関数リスト欄419に含まれる関数別に分離する(ステップ1401)。次に、複数回の呼び出しに対応するために、関数の開始位置とスタック深さを元に、1回の実行毎に分ける(ステップ1402)。以上で得られたそれぞれのトレース情報に対して、経路情報を生成する(ステップ1403)。経路情報の生成は、図9を用いて説明した関数経路情報生成処理325と同じである。

0049

図15に分岐経路情報生成の例を示す。図15(a)は、図6の擬似コードにおいて、エラー条件1(603)が成立する経路が実行された場合の分岐経路情報1501である。この場合の分岐トレースバッファの内容は、図13となる。この場合、切り出されるトレースは、IDが402から403のトレースが1つとなり、結果として経路S1が追加される。次に、図6のプログラムにおいてエラー条件2(605)が成立する経路が実行された場合分岐トレースバッファ(1510)と、それにより生成される分岐経路情報(1511)を図10(b)に示す。この場合も同様に、ID欄が502のトレースが切り出され、経路S2が追加される。さらに、図6のプログラムにおいて関数free(604)に到達する実行経路の場合の分岐トレースバッファ(1521)と分岐経路情報(1522)を示す。この場合も同様にトレースは1つであり、その結果新たに経路S3が追加される。

0050

分岐経路情報生成処理345が終了すると、分岐経路情報の取得を続けるか否かの判定を行う(ステップ350)。判定基準は、関数経路情報収集終了判定処理330と同じとする。ただし、関数リスト欄に複数の関数が登録されている場合、そのそれぞれの分岐経路情報において、条件が成り立つことを判定条件とする。

0051

分岐経路情報の取得を終了する場合、その割当管理テーブル410に対応づけられた分岐トレース対象を示すブレイクポイントが、他のエントリで利用されていない場合は、削除する。また、トレース範囲の終了点に対応しているブレイクポイントも同様に他のエントリで利用されていない場合は削除する。これにより、分岐トレースの取得が完了すると、対象プログラム101の処理は、関数トレースも分岐トレースも適用されていない状態に戻る。

0052

最後に分岐特定処理355により、取得された分岐経路情報から、メモリリークが発生している経路と発生していない経路との違いとなる分岐命令を特定する。分岐特定処理355は、分岐経路情報に対して、関数特定処理335を適用することで求めることができる。ただし、関数特定処理の図11に示すステップ1106では、見つかった事象をそのまま結果リストに追加することのみが異なる。

0053

図15(c)を例に説明する。シンボル'E'で終了する経路は、S1のみである。S1のシンボル'E'の直前のシンボルは、'location2'であり、これがシンボル'F'で終了する経路(S2, S3)に現れないかを調べる。その結果、'location2'は、経路(S3)にも現れるため、結果として、'locaiton2'が特定される。この結果、'location2'における分岐命令の条件、つまり、図6の疑似コードにおける、エラー条件1(609)により、メモリ解放漏れ(メモリリーク)が起こることが特定できる。特定した分岐命令、その分岐条件及び/又は分岐先を、要求に応じて、割当てたメモリやその割当位置と対応付けて出力する。

0054

以上の処理により、対象プログラムの実行中に、メモリ割当に関する情報を収集することでメモリリークの発生を検出し、メモリリークを起こしていると判定されたメモリ割当位置に対して、メモリリークの原因が発生している関数及び/又は分岐命令を特定することができる。

0055

なお、上記の処理において、関数トレースバッファ、及び、分岐トレースバッファの参照される最も古いエントリを管理することで、参照されなくなったバッファの内容を削除し、メモリ使用量を削減することができる。

0056

また、上記の処理においては、メモリリークと判定された割当管理テーブルのエントリ見つかると、即座に、そのエントリに対して、メモリリーク箇所の特定処理が適用される。別の方法として、メモリリークと判定されても、その判定結果を割当管理テーブルに保持しておき、一定時間経過後、あるいは、ユーザ指示、あるいは、サーバ負荷が基準値以下になった場合、あるいは、特定の時刻になった場合などに、その時までにメモリリークと判定されているエントリのすべてに対して、一斉に、メモリリーク箇所の検出処理を適用する方法も考えられる。

0057

また、対象プログラムへの負荷や、メモリ容量を考慮し、メモリリーク箇所の検出処理を適用する割当管理テーブルのエントリ数閾値を設け、ある基準値以下に制御する方式も考えられる。

図面の簡単な説明

0058

実施形態のソフトウエア構成である。
実施形態を実現する計算機のハードウェア構成図である。
メモリリーク箇所特定処理のフローチャートである。
メモリ情報テーブルの構成図である。
メモリリーク検出処理のフローチャートである。
対象プログラムの例としての疑似コードである。
関数トレース取得処理のフローチャートである。
関数トレース取得例である。
関数経路情報生成処理のフローチャートである。
関数経路情報生成の例である。
関数特定処理のフローチャートである。
分岐トレース取得処理のフローチャートである。
分岐トレースバッファの構成例である。
分岐経路情報生成処理のフローチャートである。
分岐経路情報生成の例である。

符号の説明

0059

101:対象プログラム、102:関数トレース出力部、103:バイナリ書換部、104:ラッパルーチン、105:共有メモリ、106:関数トレースバッファ、107:メモリ管理情報、108:ブレイクポイント情報、109:制御部、110:メモリ管理情報監視部、111:関数経路情報取得部、112:分岐経路情報取得部、113:分岐トレースバッファ、114:出力部、201:CPU、202:主記憶装置、203:ディスク装置、401:ブロック管理テーブル、410:割当管理テーブル。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ