The Bellicose Welsh
William fitz Osbern was created earl of Hereford during the first months of King William's reign. Orderic Vitalis ('Historia Ecclesiastica' Book IV):
"He gave William fitz Osbern, steward of Normandy, the Isle of Wight and county of Hereford, and set him up in the marches with Walter of Lacy and other proved warriors, to fight the bellicose Welsh. Since his followers would dare anything, fitz Osbern made a first attack on Brecknock [Brycheiniog], and defeated the Welsh kings Rhys, Cadwgan, Maredudd, and many others....
Orderic prefaces the above passage with the comment: "After King William had defeated the leading Mercian earls as I have related - Edwin being dead, and Morcar languishing in prison - he divided up the chief provinces of England amongst his followers, and made the humblest of the Normans men of wealth, with civil and military authority."  It is clear, though, that what follows is not necessarily confined to that specific moment (i.e. late 1071) - William fitz Osbern was actually dead by the time Morcar was incarcerated (Note). Florence of Worcester states that, when King William travelled to Normandy in Spring 1067, "he had created [William fitz Osbern] earl of Hereford". Earl William was succeeded by his son Roger. When Roger was imprisoned, following his rebellion in 1075, the earldom lapsed.
.... The king had already given the city and county of Chester to the Fleming Gerbod, but he was continually molested by the English and Welsh alike. At length he received a message from the men he had left behind in Flanders to administer his hereditary honour, urgently requiring his return, and obtained permission for a short visit from the king. But there by misfortune he fell into the hands of his enemies; and loaded with fetters and deprived of all earthly happiness he learned through long wretchedness to compose songs of lamentation. Meanwhile the king granted the county of Chester to Hugh of Avranches, son of Richard called Goz, who with Robert of Rhuddlan, Robert of Malpas, and other fierce knights, wrought great slaughter amongst the Welsh....
Presumably, King William gave Chester to Gerbod early in 1070 (Note). Hugh is generally believed to have been appointed earl of Chester in 1071. Indeed, a charter suggests he was in that position by February of that year - though an entry in the 'Handbook of British Chronology' cautions: "We have no attestation of Hugh as earl to a clearly genuine charter before 1077."
.... He [Earl Hugh] was more prodigal than generous; and went about surrounded by an army instead of a household. He kept no check on what he gave or received. His hunting was a daily devastation of his lands, for he thought more highly of fowlers and hunters than husbandsmen or monks. A slave to gluttony, he staggered under a mountain of fat, scarcely able to move. He was given over to carnal lusts and had a numerous progeny of sons and daughters by his concubines; but almost all of them died miserably in one way or another... King William gave Roger of Montgomery first of all Arundel castle and the town of Chichester; and afterwards granted him the county of Shrewsbury, a town standing on a hill above the river Severn....
Orderic says that Duke William (as he then was) had left his wife, Matilda, and Roger of Montgomery to act as regents of Normandy whilst he undertook the conquest of England. Roger came to England, with King William (as he now was), in December 1067. As with the other marcher earls, it is difficult to be precise about the date of Roger's acquisition of Shrewsbury. A charter, purportedly from 1068, is witnessed by Earl Roger. It seems reasonable, however, that Roger became earl of Shrewsbury in 1071. (Note)
.... He was a wise and prudent man, a lover of justice, who always enjoyed the company of learned and sober men. For many years he had in his household three learned clerks, Godebald, Odelerius, and Herbert, whose advice was very profitable to him. To Warin the Bald, a man small in body but great in spirit, he gave his niece Amieria and the sheriffdom of Shrewsbury, employing him to crush the Welsh and other opponents and pacify the whole province under his rule."
'Domesday Book' shows how William fitz Osbern established a line of castles from Wigmore to Chepstow, and began the process of appropriating Welsh territory.
William of Malmesbury says of William fitz Osbern: "The energy of his mind was seconded by the almost boundless liberality of his hand: hence it arose, that by the multitude of soldiers, to whom he gave extravagant pay, he repelled the rapacity of the enemy, and ensured the favour of the people. In consequence, by this boundless profusion, he incurred the king's severe displeasure; because he had improvidently exhausted his treasures. The regulations which he established in his county of Hereford, remain in full force at the present day; that is to say, that no knight should be fined more than seven shillings for whatever offence: whereas, in other provinces, for a very small fault in transgressing the commands of their lord, they pay twenty or twenty-five."
At the time when William fitz Osbern and his son (and successor) Roger were masterminding the annexation Gwent, Caradog (son of Gruffudd ap Rhydderch) was, apparently, the dominant force in south-east Wales.
Caradog was not the only king in south-east Wales. There was also Cadwgan ap Meurig, of the old ruling dynasty of Morgannwg. Wendy Davis ('Property and Power in the Early Middle Ages') writes of: "... Cadwgan ap Meurig of the old line apparently being dead by 1072 ..."  and notes that: "Cadwgan, king of Morgannwg, was last heard of granting property to Bishop Herewald in the neighbourhood of Llandaff round about 1070, and Caradog, also king, did so in Gwent a few years later."  It may be that Cadwgan ruled as a subordinate of Caradog, though, John Davies ('A History of Wales') maintains that: "... in 1074 Caradog drove Cadwgan ap Meurig from Glamorgan and seized his kingdom."  Cadwgan is not mentioned in Welsh annals, but, presumably, he is the Cadwgan said (by Orderic Vitalis, above) to have been defeated by William fitz Osbern.
In 1072, Caradog, with assistance from "the French", defeated and killed Maredudd ab Owain of Deheubarth (south-west Wales) in battle on the banks of the Rhymni. Who Caradog's Norman allies (i.e. "the French") were is not known, nor is the nature of his relationship with them. It is conceivable that Caradog was a client of the Normans, however, it is probably more likely that a temporary alliance, for mutual benefit, had been agreed (Note). At any rate, Deheubarth was targeted by the Normans in 1073, when they ravaged Ceredigion and Dyfed, and in 1074, when just Ceredigion was raided - according to the B-text of the 'Annales Cambriae', it was Roger of Montgomery's son, Hugh, who was responsible for this second raid. In 1075, Bleddyn ap Cynfyn, king of Gwynedd (northern Wales) descended on Deheubarth, and was killed in Ystrad Tywi. The 'Brut y Tywysogion' says Bleddyn:
"... was killed by Rhys ab Owain [brother of Maredudd], through the deceit of evil minded chieftains and the noblemen of Ystrad Tywi ..."
Further, the 'Brut y Tywysogion' asserts that Bleddyn - following in the footsteps of, his half-brother, Gruffudd ap Llywelyn - had:
"... nobly supported the whole kingdom of the Britons."
It seems, then, that Bleddyn was Rhys' overlord. Perhaps Rhys had lured him south - possibly requesting his assistance against the Normans or, maybe, Caradog - and then, treacherously, killed him.
"... Bleddyn ap Cynfyn, who was the mildest and most merciful of the kings, and would injure no one unless offended, and when offended, it was against his will that he then avenged the offence. He was gentle to his relations, and was defender of the orphans, the helpless, and the widows; was the supporter of the wise, the honour and stay of the churches, and the comfort of the countries; generous to all, terrible in war, and amiable in peace, and a defence to every one."
'Brut y Tywysogion'
It would appear that none of Bleddyn's sons was old enough to succeed him, so Gwynedd passed to Bleddyn's cousin, Trahaearn ap Caradog. Trahaearn, however, immediately faced opposition from Gruffudd ap Cynan - grandson of Iago ab Idwal, king of Gwynedd 1023-39 (see: Dynastic Disputes). According to the, anonymous, later-12th century, 'History of Gruffudd ap Cynan', Gruffudd was born and raised in Ireland - his mother being a daughter of the Hiberno-Norse king of Dublin (Note). In 1075, Gruffudd arrived in Anglesey. The 'History' says he landed at Abermenai, and sent requests that the worthies of Anglesey, Arfon and Llyn hurry to meet with him. This they did, and were persuaded "to help him to obtain his patrimony, because he was their rightful lord".
In the introduction to his translation of the 'History of Gruffudd ap Cynan', D. Simon Evans warns: "As a historical document its value must remain suspect. Events which do not redound to the glory of Gruffudd are studiously shunned, as it was clearly the author's intention to portray him solely as a man of prowess, honour and diplomatic acumen, whose progress was nevertheless bedevilled by constant ill-luck and treachery."  A view echoed by Kari Maund in 'The Welsh Kings': "... [the 'History of Gruffudd ap Cynan'] was not written until after his death, and may not have been official: many of the details it contains are suspect, designed as dynastic propaganda, and it is undeniably biased in its account of other Welsh leaders."
Gruffudd then travelled to:
"... the castle of Rhuddlan to Robert of Rhuddlan, a renowned, valiant baron of strength, a nephew of Hugh earl of Chester, and he besought him for help against his enemies who were in possession of his patrimony. And when Robert heard who he was, and for what he had come, and what his request was, he promised to support him."
'History of Gruffudd ap Cynan'
In Book VIII of the 'Historia Ecclesiastica', Orderic Vitalis devotes considerable space to a biography of Robert. He writes that Robert's cousin, Earl Hugh: "... appointed Robert commander of his troops, and governor of his whole province. At that time the Britons on the borders, who are commonly called Gael or Welsh, took arms with great fury against King William and all his adherents. A fortress was therefore built at Rhuddlan by the king's command, to over-awe the Welsh, and the custody of it committed to Robert that he might defend the English frontier against the inroads of those barbarians. The warlike lord-marcher had frequent encounters with that turbulent people, in which much blood was shed... For fifteen years he severely chastised the Welsh, and seized their territory ... Making inroads into their country, through woods and marshes, and over mountain heights, he inflicted losses on the enemy in every shape. Some he butchered without mercy, like herds of cattle, as soon as he came up with them. Others he threw into dungeons, where they suffered a long imprisonment, or cruelly subjected them to a shameful slavery."  There is some doubt, however, that there was a significant Norman presence as far west as Rhuddlan in 1075. Indeed, 'Domesday Book', the survey for which was carried out in 1086, notes: "In this manor of Rhuddlan a castle, likewise called Rhuddlan, has lately been built."
The 'Brut y Tywysogion' mentions that one Cynwrig ap Rhiwallon was killed by "the Gwyneddians" (i.e. the men of Gwynedd) - no leader being named. In the 'History of Gruffudd ap Cynan' story, Cynwrig ap Rhiwallon ("a petty king of Powys") and Trahaearn ap Caradog are joint rulers - Cynwrig being Trahaearn's "kinsman". Gruffudd sends out a force of his new allies, who take Cynwrig by surprise - killing him and "many of his men". Gruffudd, at the head of a "large host", then marches against Trahaearn. At "the place called in Welsh Gwaed Erw, or the Bloody Field, because of the battle which took place there", in Meirionydd, Gruffudd defeats Trahaearn - though Trahaearn manages to get away from the battlefield. At this point, the 'History' declares that:
"... Gruffudd was exalted from that day forth, and deservedly acclaimed king of Gwynedd ... Gruffudd began to settle his kingdom and to organize its people, and rule them with an iron rod gloriously in the Lord."
The battle of Gwaed Erw is not mentioned in the Welsh annals, though it is named, as one of Gruffudd's victories, in an elegy by the poet, Meilyr Brydydd.
Gruffudd then turns on Robert of Rhuddlan - managing to torch the bailey of his castle. However, the men of Llyn rebel against Gruffudd, killing some of his Irishmen. Taking heart from this, Trahaearn gathers reenforcements from Powys - he is accompanied by a Powysian, to whom the 'History' accords the title 'king', named Gwrgenau ap Seisyll (Note), and, together with the men of Llyn and other dissidents, marches against Gruffudd:
"And when Gruffudd heard of the treachery and alliance against him by his own men together with his enemies, he proceeded against them, and with him the men of Anglesey and Arfon and a few of the men of Denmark and the Irish, and a mighty battle ensued. There was great slaughter on both sides, many fell from the host of King Gruffudd, and many were captured in the battle ... King Gruffudd, however, was seated on his horse in the midst of his army, with his flashing sword mowing down both his traitors and enemies, like Agamemnon, king of Phrygia, of yore fighting Troy. And then there attacked Gruffudd, Tudur, a youth from Anglesey, the archtraitor, brandishing a spear, and he turned aside to attack him behind his saddle-bow. When Gwyncu, a baron from Anglesey, saw that, he took him [Gruffudd] against his will from the battle to his ship, which was in Abermenai. And then they went to the island of Adron, namely the island of Seals. Then they voyaged to Wexford in Ireland. That encounter from then til today is called Bron-yr-Erw, or Erw-yr-Allt from then til today."
The 'Brut y Tywysogion' simply states that "... the battle of Bron yr Erw took place between Gruffudd and Trahaearn."
The story may have been embellished, but there is no disputing the outcome - Gruffudd's bid for the throne of Gwynedd had failed (Note). Also in 1075, in the South, there took place the battle of Camddwr. Two brothers, Goronwy and Llywelyn (sons of one Cadwgan ap Elystan), in alliance with Caradog ap Gruffudd, fought against Rhys ab Owain and his ally, Rhydderch ap Caradog (who appears to have been a cousin of Caradog ap Gruffudd). Rhys and Rhydderch were victorious, but in the next year Rhydderch was killed by another cousin, Meirchion. In 1077, at the battle of Gweunytwl, Goronwy and Llywelyn were again defeated by Rhys. It is an indicator of the security of Trahaearn's position in the North, that, in 1078, he could turn his attention to the South, and tackle Rhys:
"... the battle of Pwllgwdig took place, when Trahaearn, king of Gwynedd, prevailed, and by the grace of God, avenged the blood of Bleddyn ap Cynfyn ... And there all the family of Rhys fell, and he himself became a fugitive, like a timid stag before the hounds, through the thickets and rocks."
'Brut y Tywysogion'
Late in the year, Rhys and his brother, Hywel, were slain by Caradog ap Gruffudd. It seems likely that Trahaearn and Caradog were in cahoots, and, presumably, Caradog hoped to get his hands on Deheubarth after Rhys' death. This was not to be, however. In the next year:
"... Rhys ap Tewdwr began to reign."
'Brut y Tywysogion'
Rhys' first year as king seems to have passed relatively uneventfully - a Viking raid on St.Davids being the only recorded incident (Note) - but in 1081 he was attacked by Trahaearn and Caradog. In the 'History of Gruffudd ap Cynan', Gruffudd, with "a royal fleet from Waterford", lands at Porthclais, near St.Davids. Rhys rushes to meet him (addressing him as "king of the kings of Wales"), and beg his aid. Gruffudd does not know who Rhys is, nor why he is requesting assistance. Rhys informs him that he is the king of Deheubarth, and that he is on the run from "three kings from the chief lands of Wales". The three are Trahaearn and Caradog, of course, and also Meilyr ap Rhiwallon - to whom the rule of Powys is granted (Note). Rhys promises half his territory to Gruffudd, and to do homage to him also, in return for his help. The terms are agreeable to Gruffudd, and they set out after the three kings. After "a full day's journey" they come to the kings' camps, and battle is joined:
"Gruffudd was the first fighter to go into battle like a giant and a lion, without respite scattering his opponents with a flashing sword... The shouts of the combatants were raised to the sky: the earth resounded with the tumult of horses and foot soldiers: the sound of conflict was heard from afar: the clash of arms sounded often: the men of Gruffudd fiercely putting on the pressure, and their enemies submitting to them: the sweat of their toil and the blood forming running streams. Amidst that, Trahaearn was stabbed in his bowels, until he was on the ground breathing his last, chewing with his teeth the fresh herbs and groping on top of his arms: and Gwcharki the Irishman made bacon of him as of a pig."
The 'History of Gruffudd ap Cynan' does not specifically mention that, as well as Trahaearn, Caradog and Meilyr were also killed. The site of the battle, Mynydd Carn, is not known. According to the story, after the battle, Rhys begins to fear for his own safety, and slips away. Gruffudd is not amused and has his men ravage Rhys' territory. Gruffudd then marches north to secure Gwynedd, ravaging Arwystli, which was Trahaearn's homeland, and Powys in the process:
"And there was rest and peace in Gwynedd for a few days."
Then, unfortunately for Gruffudd, he is betrayed to the Normans, who:
"... put him in the gaol of Chester, the worst of prisons, with shackles upon him, for twelve years."
Later, the 'History' implies Gruffudd's imprisonment was sixteen years. The 'History' says that Gruffudd was delivered into the hands of Earl Hugh of Chester and Hugh, the son of Roger of Montgomery. (This second Hugh is called 'earl of Shrewsbury', though he didn't become so until after Roger's death in 1094). However, in Robert of Rhuddlan's epitaph, written by Orderic Vitalis, it is Robert who is credited with Gruffudd's incarceration (Note).
"And straightway after he had been captured, Earl Hugh [of Chester] came to his territory with a multitude of forces, and built castles and strongholds after the manner of the French, and became lord over the land."
'History of Gruffudd ap Cynan'
'Domesday Book', famously, records that:
"Robert of Rhuddlan holds of the king [William] North Wales at farm for £40 ..." 
The, long-standing, union of Gwynedd and Powys was now broken ....
Powys had been annexed by Gwynedd more than two hundred years previously (Note).
.... and an independent Powys would emerge - ruled by the descendants of Bleddyn ap Cynfyn. Gruffudd ap Cynan did manage to get out of prison, but exactly when is not clear.
The 'History of Gruffudd ap Cynan' cannot agree with itself - giving the duration of his incarceration at twelve years (which would have made him free in 1093) and sixteen years (which would have made him free in 1097). However, the story of Robert of Rhuddlan's death, told by Orderic Vitalis, suggests it was earlier than either of these. According to Orderic, on 3rd July in the year, by implication, 1088, Robert attacked a pirate band, led by Gruffudd, which had landed at the Great Orme. Robert was killed, and his head was mounted atop a ship's mast as a trophy. Robert's men set off after the pirate ships, but abandoned the chase when Gruffudd and his men threw Robert's head into the sea.
Gruffudd does not feature in Welsh annals again until 1098. From then, until his death in 1137 (aged eighty-two and blind, according to the 'History'), his time was spent rebuilding the kingdom of Gwynedd.
"... Gruffudd ap Cynan died - the king and sovereign and prince and defender and pacifier of all the Welsh, after many dangers by sea and land, after innumerable spoils and victories in war, after riches of gold and silver and costly garments, after collecting together into Gwynedd, his own country, those who had been before scattered into various countries by the Normans, after building in his time many churches, and consecrating them to God, and after habiting himself as a monk, and receiving the communion of the Body of Christ, and extreme unction."
'Brut y Tywysogion'
Meanwhile, in the South, in the aftermath of the battle of Mynydd Carn, King William himself made an appearance. The only 'Anglo-Saxon Chronicle' comment for the year 1081 is:
"This year the king led an army into Wales, and there freed many hundreds of men."
The Welsh annals, however, present William's visit in a very different way:
"... William the Bastard, king of the Saxons [English] and the French [Normans] and the Britons [Welsh], came for prayer on a pilgrimage to Menevia [St.Davids]."
'Brut y Tywysogion'
Though there is no record of such a thing, it would appear that a deal was struck between William and Rhys ap Tewdwr - William recognising Rhys as ruler of Deheubarth; Rhys accepting William as his overlord. Another, frequently cited, passage in 'Domesday Book' seems to suggest that Rhys' status was similar to Robert of Rhuddlan's:
"Rhys of Wales renders to King William £40."
King William died in 1087. Soon after, Bernard of Neufmarché (from Herefordshire) began his conquest of Brycheiniog. In 1093, Rhys met his death at the hands of Bernard's Norman forces:
"Res [Rhys], king of the Welsh, during Easter week, was slain in battle near the castle of Brecknock [Brecon]."
Florence of Worcester
"... Rhys ap Tewdwr, king of Deheubarth, was killed by the French, who inhabited Brycheiniog; and then fell the kingdom of the Britons."
'Brut y Tywysogion'
Probably at about the time Bernard began his conquest of Brycheiniog, Robert fitz Hamo (from Gloucestershire) began his take-over of Morgannwg - an undertaking which seems to have been unnoticed by either Welsh or English chroniclers. This historical void is filled by a 'tradition' (Elizabethan fabrication might be nearer the mark) in which Iestyn ap Gwrgant, who is ruling Morgannwg, obtains Robert fitz Hamo's services to help him defeat Rhys ap Tewdwr. In this elaborate story, it is Iestyn and Robert who defeat and kill Rhys. Iestyn then reneges on a deal he has made with a Welsh ally, who persuades Robert to turn on Iestyn. Iestyn is defeated - Robert and his men take the best lands, leaving the residue to the Welsh.
Translations:
'History of Gruffudd ap Cynan' by D. Simon Evans
'Brut y Tywysogion' by Rev. John Williams ab Ithel
Orderic Vitalis 'Historia Ecclesiastica' Book IV by Marjorie Chibnall
Orderic Vitalis 'Historia Ecclesiastica' Book VIII by Thomas Forester
William of Malmesbury 'Gesta Regum Anglorum' by Rev. J. Sharpe, revised by Rev. J. Stevenson
Florence of Worcester 'Chronicon ex Chronicis' edited and in part translated by Joseph Stevenson