Full_Name: Jeerg Bircher Version: lmdb (master) OS: MacOS / Linux URL: ftp://ftp.openldap.org/incoming/Juerg_Bircher_160527-Access-newly-opened-database-from-another-transactio.patch Submission from: (NULL) (178.82.37.195) A transaction tracks newly opened databases and if the transaction is committed the newly opened databases are propagated to the list of open databases of the environment. However if the read only transaction is aborted the databases are not propagated. If database handles (MDB_dbi) are cached in the application to avoid calling mdb_dbi_open() there might be the situation of two threads running a read only transaction concurrently. First threads opens the database and commits the read-only transaction. The database is added to the list of open databases in the environment. The returned dbi is globally cached in the application. The second thread also wants to access the same database and finds the database handle in the global application cache. The database handle however is not valid as the transaction only uses a snapshot of open databases. So the second thread gets an EINVAL when using that database handle. This should not happen as the database is open and added to the environment. The following should fix this issue by updating the mt_numdbs and marking the delta with DB_UNUSED static int mdb_update_db_info(MDB_txn *txn, MDB_dbi dbi) { /* propagate newly opened db from env to current txn. Mark them as unused */ if (txn->mt_numdbs < txn->mt_env->me_numdbs) { memset(txn->mt_dbflags + txn->mt_numdbs, DB_UNUSED, txn->mt_env->me_numdbs - txn->mt_numdbs); } txn->mt_numdbs = txn->mt_env->me_numdbs; return dbi < txn->mt_numdbs; } /** Check \b txn and \b dbi arguments to a function and initialize db info if needed */ #define TXN_DBI_EXIST(txn, dbi, validity) \ ((txn) && ((dbi)<(txn)->mt_numdbs || mdb_update_db_info((txn), (dbi))) && (((txn)->mt_dbflags[dbi] & (validity)) || (((txn)->mt_dbflags[dbi] & DB_UNUSED) && mdb_setup_db_info((txn), (dbi), (validity))))) IMPORTANT depends ITS#8430 See also mailing list openldap-technical thread: Improved handling for large number of databases / Access newly opened database from another transaction
This works as intended. Each transaction is atomic, and shall see neither DBIs nor data which were committed after the transaction began. Cross-txn mdb_dbi_open() is in any case hairy to get right, we screwed it up several times before arriving at the now-obvious semantics. An application can open and cache its DBIs in a separate startup transaction, then commit it and start new transactions. -- Hallvard
On 27/05/16 15:11, "Hallvard Breien Furuseth" <h.b.furuseth@usit.uio.no> wrote: >This works as intended. Each transaction is atomic, and shall see >neither DBIs nor data which were committed after the transaction began. >Cross-txn mdb_dbi_open() is in any case hairy to get right, we screwed >it up several times before arriving at the now-obvious semantics. > It is fine that newly opened database handles shall not be seen by other transactions as long the transaction runs.. But once the transaction which opened the handle is committed it should be valid for any other transaction. This would greatly simplify lazy database opening of a multithreaded application. The suggested patch does exactly implement that behaviour. I believe it does not break anything. Isolation must be guaranteed for the data but not necessarily for the database handles. >An application can open and cache its DBIs in a separate startup >transaction, then commit it and start new transactions. Yes this would be a simple approach to get around that problem. But I do not like it as with each opened database the overhead increases especially if not using my suggested improvements in ITS#8430. See my measurements with the improved lmdb and the original lmdb. The test always performs 1000000 iterations on one database while having 1 database open in the first run and having all databases open in the second run. lmdb improved (renew, reset) [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 10] open databases in [0.31975] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [10 of 10] open databases in [0.20350] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 100] open databases in [0.25845] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [100 of 100] open databases in [0.29663] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 1000] open databases in [0.28590] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1000 of 1000] open databases in [0.42897] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 10000] open databases in [0.30004] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [10000 of 10000] open databases in [1.68870] seconds lmdb improved (begin, commit) [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 10] open databases in [0.36538] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [10 of 10] open databases in [0.35923] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 100] open databases in [0.34858] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [100 of 100] open databases in [0.39294] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 1000] open databases in [0.40222] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1000 of 1000] open databases in [0.54752] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 10000] open databases in [0.78595] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [10000 of 10000] open databases in [2.32414] seconds lmdb original (renew, reset) [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 10] open databases in [0.18597] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [10 of 10] open databases in [0.21572] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 100] open databases in [0.24173] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [100 of 100] open databases in [0.46497] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 1000] open databases in [0.27127] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1000 of 1000] open databases in [4.18579] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [1 of 10000] open databases in [0.30128] seconds [1000000] iterations (renew, cursor_open, cursor_close, reset) on 1 database with [10000 of 10000] open databases in [49.35048] seconds lmdb original (begin, commit) [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 10] open databases in [0.45135] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [10 of 10] open databases in [0.38990] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 100] open databases in [0.47890] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [100 of 100] open databases in [0.69917] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 1000] open databases in [1.84908] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1000 of 1000] open databases in [5.88098] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [1 of 10000] open databases in [22.12491] seconds [1000000] iterations (begin, cursor_open, cursor_close, abort) on 1 database with [10000 of 10000] open databases in [74.53854] seconds > >-- > Hallvard Regards Juerg
juerg.bircher@gmail.com wrote: > On 27/05/16 15:11, "Hallvard Breien Furuseth" <h.b.furuseth@usit.uio.no> wrote: > >> This works as intended. Each transaction is atomic, and shall see >> neither DBIs nor data which were committed after the transaction began. >> Cross-txn mdb_dbi_open() is in any case hairy to get right, we screwed >> it up several times before arriving at the now-obvious semantics. >> > > It is fine that newly opened database handles shall not be seen by > other transactions as long the transaction runs.. But once the > transaction which opened the handle is committed it should be valid > for any other transaction. It should be valid for any other transaction *that started after the opening transaction committed.* This is the nature of transactions, they are fully isolated from each other. > This would greatly simplify lazy database > opening of a multithreaded application. Allowing existing transactions to use the DBIs would break transaction isolation. That is a non-starter. > The suggested patch does exactly implement that behaviour. I believe > it does not break anything. Isolation must be guaranteed for the data > but not necessarily for the database handles. Wrong. A database handle essentially points to data. Exposing that data to a transaction that was opened before that handle's transaction was committed *does* break isolation. Violating the ACID guarantees of LMDB's transaction system is Not allowed. > >> An application can open and cache its DBIs in a separate startup >> transaction, then commit it and start new transactions. > > Yes this would be a simple approach to get around that problem. But I > do not like it as with each opened database the overhead increases > especially if not using my suggested improvements in ITS#8430. You are saying you don't like ACID transactions. If that's the case, LMDB is not for you. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/
On Sat, May 28, 2016 at 11:18 AM, Howard Chu <hyc@symas.com> wrote: > juerg.bircher@gmail.com wrote: >> >> On 27/05/16 15:11, "Hallvard Breien Furuseth" <h.b.furuseth@usit.uio.no> >> wrote: >> >>> This works as intended. Each transaction is atomic, and shall see >>> neither DBIs nor data which were committed after the transaction began. >>> Cross-txn mdb_dbi_open() is in any case hairy to get right, we screwed >>> it up several times before arriving at the now-obvious semantics. >>> >> >> It is fine that newly opened database handles shall not be seen by >> other transactions as long the transaction runs.. But once the >> transaction which opened the handle is committed it should be valid >> for any other transaction. > > > It should be valid for any other transaction *that started after the opening > transaction committed.* This is the nature of transactions, they are fully > isolated from each other. > >> This would greatly simplify lazy database >> opening of a multithreaded application. > > > Allowing existing transactions to use the DBIs would break transaction > isolation. That is a non-starter. > >> The suggested patch does exactly implement that behaviour. I believe >> it does not break anything. Isolation must be guaranteed for the data >> but not necessarily for the database handles. > > > Wrong. A database handle essentially points to data. Exposing that data to a > transaction that was opened before that handle's transaction was committed > *does* break isolation. Violating the ACID guarantees of LMDB's transaction > system is Not allowed. >> >> >>> An application can open and cache its DBIs in a separate startup >>> transaction, then commit it and start new transactions. >> >> >> Yes this would be a simple approach to get around that problem. But I >> do not like it as with each opened database the overhead increases >> especially if not using my suggested improvements in ITS#8430. > > > You are saying you don't like ACID transactions. If that's the case, LMDB is > not for you. Not at all ACID is a must and something I very much appreciate about LMDB! LMDB is definitely for me and I'm saying that after having spent nearly one intensive year with LMDB! So I like to thank you for the outstanding database. > > -- > -- Howard Chu > CTO, Symas Corp. http://www.symas.com > Director, Highland Sun http://highlandsun.com/hyc/ > Chief Architect, OpenLDAP http://www.openldap.org/project/
In ITS#8430, Juerg Bircher wrote: > So if you drop ITS#8431 it would at least be very helpful to get an > separate error like MDB_INVALID_DPI instead of EINVAL So the > application sharing and caching handles (dbi) could handle the > situation appropriate like use mdb_env_open() so that the dbi becomes > valid in that txn as well. This is ITS#8431 in a new guise, so I'm replying here. We know DBI handling is inconvenient. We'd have fixed it if it were easy without adding a bunch of locks. I'll walk through some of it below, I expect it'll be useful to have for future reference anyway: You mean like this? if (mdb_something(txn, dbi, ...) == MDB_INVALID_DBI) { /* Get <dbi>, which some other txn committed after <txn> began */ mdb_dbi_open(txn, "database name of <dbi>", 0, &dbi2); assert(dbi2 == dbi); } That breaks this requirement from the mdb_dbi_open() doc: * A transaction that uses * this function must finish (either commit or abort) before * any other transaction in the process may use this function. To fulfill that, you must serialize txns which use mdb_dbi_open(). (Unless they're all write txns, which LMDB serializes.) One reason you must, is that there is no sync anywhere else in your suggestion. Multi-threaded use of structures, like the ones behind DBIs, must be synchronized. But DBIs and mdb_dbi_open() are not mutex-protected, nor are read-only txns (after the per-thread setup). So it's up to the user. And LMDB mostly can't catch users at less than txn-sized threading bugs - like the DBI workarounds people keep trying. I suppose we should add some of the above more clearly in lmdb.h doc, since people keep trying to hack around it. And "EINVAL/MDB_BAD_DBI often indicate that LMDB detected a bug in your program, not that you can safely work around the problem when LMDB returns them." (Not always, unless we walk carefully through which error codes are returned when first.) For a txn to pick up a DBI committed after the txn started, LMDB would need to mutex-protect DBI operations. Something like this: - Add an env+txn flag MDB_ADMIN_LOCKS. If it is set in the env, then mdb_dbi_open() fails if it is not also set in the txn. The txn flag wraps DBI handling in a new mutex in txn_begin(), dbi_open(), commit/abort() of a txn which opened a DBI. The env flag wraps dbi_close() in the mutex. - Add mdb_dbi_pickup(MDB_txn*, MDB_dbi of a named DB): Pick up a DBI which was committed after the txn began. It will lock the mutex, and maybe it'll require MDB_ADMIN_LOCKS in the txn. (I don't know if pickup(main DBI) would be safe.) Maybe that's more ACID-friendly - a separate function to step outside and look at the current env. If I've gotten it right... Of course, if the txn which calls dbi_pickup() began before that named DB was created, then the txn picks up a DBI which it cannot use. That's OK as far as LMDB is concerned, it does safely catch use of a non-existent named DB. But makes it less useful to users. So I wonder, will people optimize away the mutexing in the way you suggested above? Try to use a DBI in a txn without MDB_ADMIN_LOCKS, and if that fails call mdb_dbi_pickup(). If so, they reintroduce the heisenbug: The test for whether the DBI was OK, was not mutexed vs. mdb_txn_commit(txn which created the DBI). Or simpler, the new flag could just tell MDB to wrap a mutex around every single txn_begin and txn_commit. That won't tempt anyone to optimize away locks, since there are so much locking already. But then, why are they using LMDB? LMDB has made a lot of tradeoffs to avoid locking in read-only txns. See Caveats in lmdb.h. And it'd still be unsafe to allow overlapping txns to mdb_dbi_open() the same DB. txn1 creates the DBI, txn2 opens it too, txn1 aborts but must not close the DBI because txn2 is using it... So MDB_dbx would need a refcount of how many existing txns opened the DB during DBI creation. Also I suppose ADMIN_LOCKS would need to disable mdb_set_compare() & co. A new function mdb_dbi_open2() could init the entire MDB_dbx while holding the mutex, so other txns would not use the half-initialized DBX. Alternatively, dbi_open2(named DB) above can take a flag which says "make the DBI immediately available in the MDB_env". That'll be unsafe for txns where the user does not synchronize txn_begin against the dbi_open2(). And it has its own sets of issues with multiple txns opening a DB, nested txns, etc. Then there's another approach: "Transactions are isolated from each other, provided you use LMDB correctly. That's all. Sorry about the DBI inconveniences."
On Mon, May 30, 2016 at 2:44 PM, Hallvard Breien Furuseth <h.b.furuseth@usit.uio.no> wrote: > In ITS#8430, Juerg Bircher wrote: >> >> So if you drop ITS#8431 it would at least be very helpful to get an >> separate error like MDB_INVALID_DPI instead of EINVAL So the >> application sharing and caching handles (dbi) could handle the >> situation appropriate like use mdb_env_open() so that the dbi becomes >> valid in that txn as well. > > > This is ITS#8431 in a new guise, so I'm replying here. We know DBI > handling is inconvenient. We'd have fixed it if it were easy without > adding a bunch of locks. I'll walk through some of it below, I expect > it'll be useful to have for future reference anyway: > > > You mean like this? > > if (mdb_something(txn, dbi, ...) == MDB_INVALID_DBI) { > /* Get <dbi>, which some other txn committed after <txn> began */ > mdb_dbi_open(txn, "database name of <dbi>", 0, &dbi2); > assert(dbi2 == dbi); > } > > That breaks this requirement from the mdb_dbi_open() doc: > > * A transaction that uses > * this function must finish (either commit or abort) before > * any other transaction in the process may use this function. > Just to illustrate the simplified sequence of calls (using MDB_NOTLS): mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); mdb_txn_begin(env, NULL, MDB_RDONLY, &txn); MDB_dbi dbi; mdb_dbi_open(txn, "db1", 0, &dbi); // dbi becomes now valid and is propagated to the env mdb_txn_commit(txn); // At this point dbi for txn2 is invalid as txn2 started before opening the database if (mdb_something(txn2, dbi, ...) == MDB_INVALID_DBI) { MDB_dbi dbi2; mdb_dbi_open(txn2, "db1", 0, &dbi2); assert(dbi2 == dbi); // now dbi is valid for txn2 as with the mdb_dbi_open we propagated it to txn2! mdb_something(txn2, dbi, ...); } mdb_txn_commit(txn2); This code is really not preferred and is only a workaround. > To fulfill that, you must serialize txns which use mdb_dbi_open(). > (Unless they're all write txns, which LMDB serializes.) One reason > you must, is that there is no sync anywhere else in your suggestion. > > Multi-threaded use of structures, like the ones behind DBIs, must be > synchronized. But DBIs and mdb_dbi_open() are not mutex-protected, > nor are read-only txns (after the per-thread setup). So it's up to > the user. And LMDB mostly can't catch users at less than txn-sized > threading bugs - like the DBI workarounds people keep trying. > > I suppose we should add some of the above more clearly in lmdb.h doc, > since people keep trying to hack around it. And "EINVAL/MDB_BAD_DBI > often indicate that LMDB detected a bug in your program, not that you > can safely work around the problem when LMDB returns them." > (Not always, unless we walk carefully through which error codes are > returned when first.) > > > For a txn to pick up a DBI committed after the txn started, LMDB > would need to mutex-protect DBI operations. Something like this: > > - Add an env+txn flag MDB_ADMIN_LOCKS. If it is set in the env, > then mdb_dbi_open() fails if it is not also set in the txn. > The txn flag wraps DBI handling in a new mutex in txn_begin(), > dbi_open(), commit/abort() of a txn which opened a DBI. > The env flag wraps dbi_close() in the mutex. > > - Add mdb_dbi_pickup(MDB_txn*, MDB_dbi of a named DB): Pick up a DBI > which was committed after the txn began. It will lock the mutex, > and maybe it'll require MDB_ADMIN_LOCKS in the txn. > (I don't know if pickup(main DBI) would be safe.) > > Maybe that's more ACID-friendly - a separate function to step > outside and look at the current env. If I've gotten it right... > > Of course, if the txn which calls dbi_pickup() began before that > named DB was created, then the txn picks up a DBI which it cannot > use. That's OK as far as LMDB is concerned, it does safely catch > use of a non-existent named DB. But makes it less useful to users. > > So I wonder, will people optimize away the mutexing in the way you > suggested above? Try to use a DBI in a txn without MDB_ADMIN_LOCKS, > and if that fails call mdb_dbi_pickup(). If so, they reintroduce > the heisenbug: The test for whether the DBI was OK, was not mutexed > vs. mdb_txn_commit(txn which created the DBI). > > Or simpler, the new flag could just tell MDB to wrap a mutex around > every single txn_begin and txn_commit. That won't tempt anyone to > optimize away locks, since there are so much locking already. But > then, why are they using LMDB? LMDB has made a lot of tradeoffs to > avoid locking in read-only txns. See Caveats in lmdb.h. > > > And it'd still be unsafe to allow overlapping txns to mdb_dbi_open() > the same DB. txn1 creates the DBI, txn2 opens it too, txn1 aborts but > must not close the DBI because txn2 is using it... So MDB_dbx would > need a refcount of how many existing txns opened the DB during DBI > creation. Also I suppose ADMIN_LOCKS would need to disable > mdb_set_compare() & co. A new function mdb_dbi_open2() could init the > entire MDB_dbx while holding the mutex, so other txns would not use > the half-initialized DBX. > > Alternatively, dbi_open2(named DB) above can take a flag which says > "make the DBI immediately available in the MDB_env". That'll be > unsafe for txns where the user does not synchronize txn_begin against > the dbi_open2(). And it has its own sets of issues with multiple > txns opening a DB, nested txns, etc. > > > Then there's another approach: "Transactions are isolated from each > other, provided you use LMDB correctly. That's all. Sorry about > the DBI inconveniences." > If I got it right it is all about protecting against invalid DBIs which can happen for example if someone closes database "A" which was assigned DBI "5" and later the database "B" is opened and the free slot 5 is then assigned to "B". So we could be misled using DBI "5" having in mind database "A". So why don't we extend the MDB_DBI by adding the sequence in the lower or higher bits. When addressing the slot we simply strip the sequence bits and verify the slot's sequence against the sequence in the MDB_DBI to ensure the DBI has not changed. So picking up a DPI (as suggested in the patch) can be verified. The restriction with mdb_dbi_open() will stay. But the following would work: MDB_dbi dbi; mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); mdb_txn_begin(env, NULL, MDB_RDONLY, &txn1); mdb_dbi_open(txn1, "db1", 0, &dbi); // dbi becomes now valid and is propagated to the env // ==> and therefore is also valid for any other transaction! mdb_txn_commit(txn1); // use dbi opened in txn1 (which is committed) mdb_something(txn2, dbi, ...); .... mdb_txn_commit(txn2); So the patch could look something like that. static int mdb_update_db_info(MDB_txn *txn, MDB_dbi dbi) { unsigned int dbi_index = dbi & MDB_DBI_INDXE_MASK; unsigned int dbi_seq = dbi & MDB_DBI_SEQ_MASK << 16; if (txn->mt_env->me_dbiseqs[dbi_index] != dbi_seq) { return 0; } /* propagate newly opened db from env to current txn. Mark them as unused */ if (txn->mt_numdbs < txn->mt_env->me_numdbs) { memset(txn->mt_dbflags + txn->mt_numdbs, DB_UNUSED, txn->mt_env->me_numdbs - txn->mt_numdbs); } txn->mt_numdbs = txn->mt_env->me_numdbs; return dbi_index < txn->mt_numdbs; }
On 30. mai 2016 18:08, Juerg Bircher wrote: > If I got it right it is all about protecting against invalid DBIs > which can happen for example if someone closes database "A" which was > assigned DBI "5" and later the database "B" is opened and the free > slot 5 is then assigned to "B". So we could be misled using DBI "5" > having in mind database "A". > > So why don't we extend the MDB_DBI by adding the sequence in the lower > or higher bits. (...) Ugh. I didn't expect all my words to miss that badly. Yes, you caught one issue. There are more. The central point is what I wrote here: >> Multi-threaded use of structures, like the ones behind DBIs, must be >> synchronized. But DBIs and mdb_dbi_open() are not mutex-protected, >> nor are read-only txns (after the per-thread setup). So it's up to >> the user. And LMDB mostly can't catch users at less than txn-sized >> threading bugs - like the DBI workarounds people keep trying. I shouldn't really be the one to answer this, Howard might answer differently if he didn't just fetch a flamethrower. But anyway: It's about keeping a clean model of what is going on, which helps understanding and correctly coding both LMDB itself and user programs. When you don't work against the model, anyway. It's about keeping LMDB's internal data structures consistent. LMDB must know what the heck is going on when it manages and uses DBIs. Things like ensuring that two threads do not run mdb_dbi_open() at the same time, overwriting each others' work and creating a mess. It's about LMDB being able to know it delivers correct results, at least if the user doesn't work too hard at thwarting it. This usually means serializing various parts of the code using locks or something similar. But for the sake of speed and simplicity, LMDB has no relevant locks. It relies on the user to lock and has some code to catch some locking errors. One key word is "tries" - without locks or other expensive code, it can't always catch them even when it does try. So DBI errors are not "this DBI is broken, so drop/refresh it" but "your program is buggy, so fix it". And it's about living with the design choices and tradeoffs which LMDB has made, e.g. not slowing down read-only txns for anything like locking or extensive error checking. So anyway, this ITS is about changes to LMDB which will not happen. Instead it reminded me to add some checks for user errors with DBIs. -- Hallvard